SPOJ 375-Query on a tree(ツリー分割テンプレートの詳細と入門)

4899 ワード
アルゴリズム 線分樹 データ構造 夏休みのトレーニング+個人復習 SPOJ 木の鎖が分断する
You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3...N-1.
We will ask you to perfrom some instructions of the following form:
  • CHANGE i ti : change the cost of the i-th edge to ti or
  • QUERY a b : ask for the maximum edge cost on the path from node a to node b

    • Input
    The first line of input contains an integer t, the number of test cases (t <= 20). t test cases follow.
    For each test case:
  • In the first line there is an integer N (N <= 10000),
  • In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of cost c (c<= 1000000),
  • The next lines contain instructions "CHANGE i ti" or "QUERY a b",
  • The end of each test case is signified by the string "DONE".

    • There is one blank line between successive tests.
    Output
    For each "QUERY"operation, write one integer representing its result.
    Example 
    Input:
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

Output:
1
3

    簡単なツリーチェーン断面テンプレートの問題.2時間も木の鎖の断分を見てやっと理解した.
    入門したい方はこのブログをお勧めします.http://blog.sina.com.cn/s/blog_6974c8b20100zc61.html
    他はコードを見ることができますが、注釈は詳しく書かれているような気がします.何か問題があったら、伝言を残してできるだけ早く答えてください.
    #include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 20010;
struct Edge
{
    int to,next;
}edge[MAXN*2];
int head[MAXN],tot;

int top[MAXN];//top[v]  v          
int fa[MAXN]; //    
int deep[MAXN];//  
int num[MAXN];//num[v]   v         
int p[MAXN];//p[v]  v                 
int fp[MAXN];// p    
int son[MAXN];//   
int pos;

int n;

void init()
{
    tot = 0;
    memset(head,-1,sizeof(head));
    pos = 1;//      1  ？
    memset(son,-1,sizeof(son));
}
void addedge(int u,int v)
{
    edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++;
}
void dfs1(int u,int pre,int d) //   dfs  fa,deep,num,son
{
    deep[u] = d;
    fa[u] = pre;
    num[u] = 1;
    for(int i = head[u];i != -1; i = edge[i].next)
    {
        int v = edge[i].to;
        //        ，          
        if(v != pre)
        {
            //             ，   ，        
            dfs1(v,u,d+1);
            //  u       
            num[u] += num[v];
            if(son[u] == -1 || num[v] > num[son[u]])//     
                son[u] = v;
        }
    }
}

//         ,top[u]=u，       ，  son[v]!=-1,  top[v]=top[son[v]]
void getpos(int u,int sp) //   dfs  top p
{
    top[u] = sp;
    //     
    if(son[u] != -1)
    {
        //         
        p[u] = pos++;
        //fp    p    ？
        fp[p[u]] = u;
        //     
        getpos(son[u],sp);
    }
    //        
    else
    {
        //    dfs
        p[u] = pos++;
        fp[p[u]] = u;
        return;
    }
    //       
    for(int i = head[u] ; i != -1; i = edge[i].next)
    {
        int v = edge[i].to;
        if(v != son[u] && v != fa[u])
            getpos(v,v);
    }
}

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int MAX[MAXN<<2];
int val[MAXN<<2];

void pushup(int rt){
    MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
}

void build(int l,int r,int rt){
    if(l==r){
        MAX[rt]=val[l];
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}

void update(int p,int x,int l,int r,int rt){
    if(l==r){
        MAX[rt]=x;
        return;
    }
    int m=(l+r)>>1;
    if(p<=m)
        update(p,x,lson);
    else
        update(p,x,rson);
    pushup(rt);
}

int query(int L,int R,int l,int r,int rt){
    if(l>=L&&r<=R){
        return MAX[rt];
    }
    int m=(l+r)>>1;
    int res=0;
    if(m>=L)
        res=max(res,query(L,R,lson));
    if(R>m)
        res=max(res,query(L,R,rson));
    return res;
}

int _find(int u,int v){
    int f1=top[u],f2=top[v];//              ，      ，     
    int temp=0;
    while(f1!=f2){
        //          
        if(deep[f1]deep[v])
        swap(u,v);
    return max(temp,query(p[son[u]],p[v],1,n,1));
}

int e[MAXN][3];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        init();
        scanf("%d",&n);
        getchar();
        for(int i=0;i
    Androidデザインモデル---テンプレートデザインモデル
    C#アルゴリズム入門から走路第1章:リニアメーターのループチェーンテーブル