poj 3237 Treeツリーチェーンは、ダイナミックツリーLCTを分割します.

Tree
Time Limit: 5000 MS
 
メモリLimit: 131313722 K
Total Submissions: 6171
 
Acceepted: 1687
Description
You are given a tree with N nodes.The tree’s nodes are numberred 1 through N and its edges are numbert 1 through N −1.Each edge is assited with a weight.The n you are to execute a series of instructions on the tree.The instructions can be one of the following forms:CHANGE i v
Change the weight of the ith edge to vNEGATE a. b
Negate the weight of everedge on the path from a. ト bQUERY a. b
Find the maximm weight of edges on the path from a. ト b
Input
The input contains multiple test cases.The first line of input contains an integer t (t ≤20)the number of test cases.The n follow the test cases.
Each test case is preceded by an empty line.The first nonempty line of its contains N (N ≤10,000).The next N −1 lines each contains three integers a, b and c,describing an edge connecting nodes a. and b with weight c.The edges are numberd in the order the y appar in the input.Below them ar the instructions,each sticking to the specification above.A lins with the word“DONE”ends the test case.
Output
For each「QUERY」instruction、output the result on a separate line.
Sample Input

1

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

Sample Output

1
3

ソurce
POJ Monthly-207.6.03、Lei、Tao
LCTでチェーンを維持して、チェーンの中の最大値と最小値を記録して、フラグで反対を取りますか?
逆を取れば最大値=-の最小値、最小値=-最大値を更新します.
lCTは他のブログを参照してください.

#include
#include
#include
#include
#include
using namespace std;
#define maxn 500007
#define inf  1000000000
#define ll int

struct Node{
    Node *fa,*ch[2];
    bool rev,root,flag,ty;
    int val;
    ll minv,mav;
};
Node pool[maxn];
Node *nil,*tree[maxn],*road[maxn];
int cnt = 0;
void init(){
    cnt = 1;
    nil = tree[0] = pool;
    nil->ch[0] = nil->ch[1] = nil;
    nil->val = 0;
    nil->minv = -inf;
    nil->ty = 0;
    nil->flag = 0;
}
Node *newnode(int val,Node *f){
    pool[cnt].fa = f;
    pool[cnt].ch[0]=pool[cnt].ch[1]=nil;
    pool[cnt].rev = false;
    pool[cnt].root = true;
    pool[cnt].val = val;
    pool[cnt].minv = pool[cnt].mav = val;
    pool[cnt].flag = 0;
    return &pool[cnt++];
}

//      ******        
void update_rev(Node *x){
    if(x == nil) return ;
    x->rev = !x->rev;
    swap(x->ch[0],x->ch[1]);
}
void set_negate(Node *x){
    if(x == nil) return ;
    x->flag = !x->flag;
    swap(x->minv,x->mav);
    x->minv = -x->minv;
    x->mav = -x->mav;
}
//splay      ******
void update(Node *x){
    if(x == nil) return ;
    if(x->ty == 0) x->minv = inf,x->mav = -inf;
    else x->minv = x->val,x->mav = x->val;
    if(x->ch[0] != nil){
        x->minv = min(x->minv,x->ch[0]->minv);
        x->mav = max(x->mav,x->ch[0]->mav);
    }
    if(x->ch[1] != nil){
        x->minv = min(x->minv,x->ch[1]->minv);
        x->mav = max(x->mav,x->ch[1]->mav);
    }
}

//splay    ******
void pushdown(Node *x){
    if(x == nil) return ;
    if(x->rev != false){
        update_rev(x->ch[0]);
        update_rev(x->ch[1]);
        x->rev = false;
    }
    if(x->flag != false){
        x->val = -x->val;
        set_negate(x->ch[0]);
        set_negate(x->ch[1]);
        x->flag = false;
    }
}
//splay root-->x       ******
void push(Node *x){
    if(!x->root) push(x->fa);
    pushdown(x);
}
//   x   splay      ******
void rotate(Node *x){
    Node *f = x->fa, *ff = f->fa;
    int t = (f->ch[1] == x);
    if(f->root)
        x->root = true, f->root = false;
    else ff->ch[ff->ch[1] == f] = x;
    x->fa = ff;
    f->ch[t] = x->ch[t^1];
    x->ch[t^1]->fa = f;
    x->ch[t^1] = f;
    f->fa = x;
    update(f);
}
//   x   x  splay    ******
void splay(Node *x){
    push(x);
    Node *f, *ff;
    while(!x->root){
        f = x->fa,ff = f->fa;
        if(!f->root)
            if((ff->ch[1]==f)&&(f->ch[1] == x)) rotate(f);
            else rotate(x);
        rotate(x);
    }
    update(x);
}
// x          path******
Node *access(Node *x){
    Node *y = nil,*z;
    while(x != nil){
        splay(x);
        x->ch[1]->root = true;
        (x->ch[1] = y)->root = false;
        update(x);
        y = x;
        x = x->fa;
    }
    return y;
}
//   x    ******
void be_root(Node *x){
    access(x);
    splay(x);
    update_rev(x);
}
// x     f ******
void link(Node *x, Node *f){
    be_root(x);
    x->fa = f;
}
char word[30];
int main(){
    int n,q,s,t;
    Node*x,*y,*z;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        init();
        int u,v,t;
        for(int i = 1;i <= n; i++){
            tree[i] = newnode(0,nil);
            tree[i]->ty = 0;
            update(tree[i]);
        }
        for(int i = 1;i < n ;i++){
            scanf("%d%d%d",&u,&v,&t);
            road[i] = newnode(t,nil);
            road[i]->ty = 1;
            update(road[i]);
            link(tree[u],road[i]);
            link(tree[v],road[i]);
        }
        while(1){
            scanf("%s",word);
            if(word[0] == 'D') break;
            scanf("%d%d",&u,&v);
            if(word[0] == 'Q'){
                be_root(tree[u]);
                x = access(tree[v]);
                printf("%d
",x->mav);
            }
            else if(word[0] == 'C'){
                be_root(road[u]);
                road[u]->val = v;
                update(road[u]);
            }
            else if(word[0] == 'N'){
                be_root(tree[u]);
                x = access(tree[v]);
                set_negate(x);
            }
        }
    }
    return 0;
}

/*
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
N 1 3
Q 1 2

*/