这道题很久以前用树链剖分写的，最近在学LCT ,就用LCT再写了一遍，也有一些收获。
因为这道题点权可以是负数，所以在update时就要注意一下，因为平时我的0节点表示空，它的点权为0，这样可以处理点权为非负求最大值和求和的情况（即不用特判某个点是否有左右儿子，直接更新就行了），但这道题就不行（求和要求它为0，求最大值要求它为-oo）。所以就必须特判~~~~
综上：若0号节点存在一个不可能成为答案（在求最大值时是-oo，求最小值时是+oo）或对答案没有贡献的值（在求和时是0）时，初始化时将0节点的权值设为该值，更新时就可以不用特判某个点是否为0。否则引用左右儿子值时就必须特判某个节点是否有左右儿子。
LCT用的时间大概是树链剖分的两倍。
树链剖分：
1 /************************************************************** 2 Problem: 1036 3 User: idy002 4 Language: C++ 5 Result: Accepted 6 Time:2880 ms 7 Memory:5116 kb 8 ****************************************************************/ 9 10 #include11 #include 12 #define lson rt<<1 13 #define rson rt<<1|1 14 #define inf 300000000 15 #define maxn 30001 16 using namespace std; 17 18 int n; 19 vector g[maxn]; 20 int wght[maxn], siz[maxn], son[maxn], pre[maxn], dep[maxn], top[maxn], vid[maxn], vcnt; 21 int smax[maxn<<2], ssum[maxn<<2]; 22 23 void up_sum( int pos, int v, int rt, int l, int r ) { 24 if( l==r ) { 25 ssum[rt] = v; 26 return; 27 } 28 int mid=(l+r)>>1; 29 if( mid>=pos ) up_sum( pos, v, lson, l, mid ); 30 else up_sum( pos, v, rson, mid+1, r ); 31 ssum[rt] = ssum[lson] + ssum[rson]; 32 } 33 void up_max( int pos, int v, int rt, int l, int r ) { 34 if( l==r ) { 35 smax[rt] = v; 36 return; 37 } 38 int mid=(l+r)>>1; 39 if( mid>=pos ) up_max( pos, v, lson, l, mid ); 40 else up_max( pos, v, rson, mid+1, r ); 41 smax[rt] = max( smax[lson], smax[rson] ); 42 } 43 int qu_sum( int L, int R, int rt, int l, int r ) { 44 if( L<=l && r<=R ) return ssum[rt]; 45 int mid=(l+r)>>1, re=0; 46 if( mid>=L ) re+=qu_sum(L,R,lson,l,mid); 47 if( mid+1<=R ) re+=qu_sum(L,R,rson,mid+1,r); 48 return re; 49 } 50 int qu_max( int L, int R, int rt, int l, int r ) { 51 if( L<=l && r<=R ) return smax[rt]; 52 int mid=(l+r)>>1, re=-inf; 53 if( mid>=L ) re = qu_max( L,R,lson,l,mid); 54 if( mid+1<=R ) re = max( re, qu_max( L,R,rson,mid+1,r ) ); 55 return re; 56 } 57 void dfs1( int u ) { 58 siz[u] = 1, son[u] = 0; 59 for( int t=0; t<(int)g[u].size(); t++ ) { 60 int v=g[u][t]; 61 if( v==pre[u] ) continue; 62 pre[v] = u; 63 dep[v] = dep[u]+1; 64 dfs1(v); 65 siz[u] += siz[v]; 66 son[u] = siz[v]>siz[son[u]] ? v : son[u]; 67 } 68 } 69 void dfs2( int u, int tp ) { 70 vid[u] = ++vcnt, top[u] = tp; 71 if( son[u] ) dfs2(son[u],tp); 72 for( int t=0; t<(int)g[u].size(); t++ ) { 73 int v=g[u][t]; 74 if( v==pre[u] || v==son[u] ) continue; 75 dfs2(v,v); 76 } 77 } 78 void build() { 79 pre[1] = 1, dep[1] = 1; 80 dfs1(1); 81 vcnt = 0; 82 dfs2(1,1); 83 for( int i=1; i<=n; i++ ) { 84 up_sum( vid[i], wght[i], 1, 1, vcnt ); 85 up_max( vid[i], wght[i], 1, 1, vcnt ); 86 } 87 } 88 void update( int v, int val ) { 89 up_sum( vid[v], val, 1, 1, vcnt ); 90 up_max( vid[v], val, 1, 1, vcnt ); 91 } 92 int query_sum( int u, int v ) { 93 int r=0; 94 while( top[u]!=top[v] ) { 95 if( dep[top[u]]
LCT:
1 /************************************************************** 2 Problem: 1036 3 User: idy002 4 Language: C++ 5 Result: Accepted 6 Time:5816 ms 7 Memory:2932 kb 8 ****************************************************************/ 9 10 #include11 #include 12 #define maxn 30010 13 #define oo 0x3f3f3f3f 14 using namespace std; 15 16 namespace L { 17 int pnt[maxn], pre[maxn], son[maxn][2], val[maxn], mxv[maxn], sum[maxn], rtg[maxn]; 18 19 void update( int u ) { 20 mxv[u] = sum[u] = val[u]; 21 int ls = son[u][0], rs = son[u][1]; 22 if(ls) { 23 mxv[u] = max( mxv[u], mxv[ls] ); 24 sum[u] += sum[ls]; 25 } 26 if(rs) { 27 mxv[u] = max( mxv[u], mxv[rs] ); 28 sum[u] += sum[rs]; 29 } 30 } 31 void rotate( int u, int d ) { 32 int p = pre[u]; 33 int s = son[u][!d]; 34 int ss = son[s][d]; 35 son[u][!d] = ss; 36 son[s][d] = u; 37 if( p ) son[p][ u==son[p][1] ] = s; 38 else pnt[s] = pnt[u]; 39 pre[u] = s; 40 pre[ss] = u; 41 pre[s] = p; 42 update( u ); 43 update( s ); 44 } 45 void pushdown( int u ) { 46 if( rtg[u] ) { 47 int &ls = son[u][0], &rs = son[u][1]; 48 swap( ls, rs ); 49 rtg[ls] ^= 1; 50 rtg[rs] ^= 1; 51 rtg[u] = 0; 52 } 53 } 54 void big_push( int u ) { 55 if( pre[u] ) big_push(pre[u]); 56 pushdown( u ); 57 } 58 void splay( int u, int top=0 ) { 59 big_push( u ); 60 while( pre[u]!=top ) { 61 int p = pre[u]; 62 int nl = u==son[p][0]; 63 if( pre[p]==top ) { 64 rotate( p, nl ); 65 } else { 66 int pp = pre[p]; 67 int pl = p==son[pp][0]; 68 if( nl==pl ) { 69 rotate( pp, pl ); 70 rotate( p, nl ); 71 } else { 72 rotate( p, nl ); 73 rotate( pp, pl ); 74 } 75 } 76 } 77 } 78 void access( int nd ) { 79 int u = nd; 80 int v = 0; 81 while( u ) { 82 splay( u ); 83 int s = son[u][1]; 84 pre[s] = 0; 85 pnt[s] = u; 86 pre[v] = u; 87 son[u][1] = v; 88 update(u); 89 v = u; 90 u = pnt[u]; 91 } 92 splay( nd ); 93 } 94 int findroot( int u ) { 95 while( pre[u] ) u = pre[u]; 96 while( pnt[u] ) { 97 u = pnt[u]; 98 while( pre[u] ) u = pre[u]; 99 }100 return u;101 }102 void makeroot( int u ) {103 access( u );104 rtg[u] ^= 1;105 }106 void link( int u, int v ) {107 makeroot( u );108 makeroot( v );109 pnt[u] = v;110 }111 void up_val( int u, int w ) {112 splay( u );113 val[u] = w;114 update( u );115 }116 int qu_max( int u, int v ) {117 makeroot( u );118 access( v );119 if( son[v][0] ) return max( val[v], mxv[son[v][0]] );120 else return val[v];121 }122 int qu_sum( int u, int v ) {123 makeroot( u );124 access( v );125 if( son[v][0] ) return val[v] + sum[son[v][0]];126 else return val[v];127 }128 };129 130 int n, q;131 132 int main() {133 scanf( "%d", &n );134 for( int i=2,u,v; i<=n; i++ ) {135 scanf( "%d%d", &u, &v );136 L::link(u,v);137 }138 for( int i=1,w; i<=n; i++ ) {139 scanf( "%d", &w );140 L::up_val(i,w);141 }142 scanf( "%d", &q );143 while( q-- ) {144 char ch[20];145 int u, v, w;146 scanf( "%s", ch );147 if( ch[0]=='C' ) {148 scanf( "%d%d", &u, &w );149 L::up_val( u, w );150 } else if( ch[1]=='M' ) {151 scanf( "%d%d", &u, &v );152 printf( "%d\n", L::qu_max( u, v ) );153 } else {154 scanf( "%d%d", &u, &v );155 printf( "%d\n", L::qu_sum( u, v ) );156 }157 }158 }159 160