Tree

Time Limit: 5000MS		Memory Limit: 131072K
Total Submissions: 3836		Accepted: 1088

Description

You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N − 1. Each edge is associated with a weight. Then 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 v
NEGATE a b	Negate the weight of every edge on the path from a to b
QUERY a b	Find the maximum weight of edges on the path from a to b

Input

The input contains multiple test cases. The first line of input contains an integer t (t ≤ 20), the number of test cases. Then 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 numbered in the order they appear in the input. Below them are the instructions, each sticking to the specification above. A lines with the word “DONE” ends the test case.

Output

For each “QUERY” instruction, output the result on a separate line.

Sample Input

131 2 12 3 2QUERY 1 2CHANGE 1 3QUERY 1 2DONE

Sample Output

13

树链剖分~

然后注意一下 有n-1条边。。每条边要addedge 两次 然后，注意一下空间开两倍就可以了。否则RE

只要记录最小最大值。

取反的时候把最小最大交换一下  ，然后在取负就可以了

还有lazy更新那个取反

pushdown的时候要注意一下把孩子的lazy取反

 

 

 

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define root 1,n,1#define lr rt<<1#define rr rt<<1|1#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1const int inf=1e9;const int N=20010;struct node{    int u,v,w;}e[N];int n;int top[N],rnk[N],fa[N],p[N],son[N],siz[N],dep[N],pos;int eh[N],et[N],nxt[N],tot;void init(){    memset(eh,-1,sizeof eh);    memset(son,-1,sizeof son);    pos=1;    tot=0;}void addedge(int u,int v){    et[tot]=v;nxt[tot]=eh[u];eh[u]=tot++;    et[tot]=u;nxt[tot]=eh[v];eh[v]=tot++;}void dfs1(int u,int father,int d){    fa[u]=father;    dep[u]=d;    siz[u]=1;    for(int i=eh[u]; ~i ;i=nxt[i]){        int v=et[i];        if( v==fa[u] )continue;        dfs1( v,u,d+1 ); 　　　　　siz[u] += siz[v] ;        if( son[u]==-1 || siz[v] > siz[ son[u] ] )            son[u]=v;    }}void dfs2(int u,int tp){    top[u]=tp;    p[u]=pos++;    rnk[ p[u] ]=u;    if( son[u] == -1 ) return ;    dfs2( son[u],tp );    for(int i=eh[u]; ~i ;i=nxt[i] ){        int v=et[i];        if( v==fa[u] || v==son[u] )continue;        dfs2(v,v);    }}//-----------------------------------int d_m[N<<2],d_M[N<<2];bool lazy[N<<2];void build(int l,int r,int rt){    d_m[rt]=d_M[rt]=lazy[rt]=0;    if(l==r){
   return ;}    int mid=(l+r)>>1;    build(lson);    build(rson);}void Up(int rt){    d_m[rt]=min( d_m[lr],d_m[rr] );    d_M[rt]=max( d_M[lr],d_M[rr] );}void Down(int l,int r,int rt){    if(l==r)return ;    if( lazy[rt] ) {        swap(d_m[rr],d_M[rr]);        d_M[rr] = -d_M[rr];        d_m[rr] = -d_m[rr];        lazy[rr] ^= 1;        swap(d_m[lr],d_M[lr]);        d_M[lr] = -d_M[lr];        d_m[lr] = -d_m[lr];        lazy[lr] ^= 1;    lazy[rt]=0;    }}void update(int l,int r,int rt,int x,int v){    if(l==r){        d_m[rt]=d_M[rt]=v;lazy[rt]=0;        return ;    }    Down(l,r,rt);    int mid=(l+r) >> 1;    if(x <= mid )        update(lson,x,v);    else        update(rson,x,v);    Up(rt);}int query(int l,int r,int rt,int L,int R){    int res = -inf;    if(L <= l && r<=R ){        return d_M[rt];    }    Down(l,r,rt);    int mid=(l+r)>>1;    if( L <= mid )res=max( res,query(lson,L,R) );    if( R  > mid )res=max( res,query(rson,L,R) );    return res;}void nega(int l,int r,int rt,int L,int R){    if( L <= l && r<= R ){        swap(d_m[rt],d_M[rt]);        d_M[rt] = -d_M[rt];        d_m[rt] = -d_m[rt];        lazy[rt] ^= 1;        return ;    }    Down(l,r,rt);    int mid=(l+r) >> 1;    if( L <= mid ) nega(lson,L,R);    if( R > mid ) nega(rson,L,R);    Up(rt);}int Q(int u,int v){    int res = -inf;    int f1=top[u],f2=top[v];    while(f1 != f2){        if(dep[f1] < dep[f2]){            swap(f1,f2);            swap(u,v);        }        res=max(res,query(root,p[f1],p[u]));        u = fa[ f1 ];        f1 = top[ u ];    }    if( u == v )return res;    if( dep[u] > dep[v] )swap(u,v);    return max( res , query( root,p[ son[u] ] ,p[v] ) );}void NE(int u,int v){    int f1=top[u],f2=top[v];    while(f1 != f2){        if(dep[f1] < dep[f2]){            swap(f1,f2);            swap(u,v);        }        nega(root,p[f1],p[u]);        u = fa[ f1 ];        f1 = top[ u ];    }    if( u == v )return ;    if( dep[u] > dep[v] )swap(u,v);    nega( root,p[ son[u] ] ,p[v]) ;}void run(){    char op[10];    int x,y,v;    init();    scanf("%d",&n);    for(int i=1;i
         
          < n ;++i){        if( dep[e[i].u] > dep[ e[i].v] )swap(e[i].u,e[i].v);        update(root,p[ e[i].v ],e[i].w);    }    while(scanf("%s",op)){        if(op[0] == 'D')break;        scanf("%d%d",&x,&y);        if(op[0]=='C'){            update( root, p[ e[ x ].v ]  , y );        }        else if(op[0]=='Q'){            printf("%d\n",Q(x,y));        }        else {            NE(x,y);        }    }}int main(){    int _;    #ifdef LOCAL        freopen("in.txt","r",stdin);    #endif    scanf("%d",&_);    while(_--)run();    return 0;}