树链剖分模版吧。。。
1 #include 2 #define l(a) ((a)<<1) 3 #define r(a) (((a)<<1)+1) 4 #define Rep(i,a) for(int i=0;i
e[maxn]; 27 void dfs(int x){ 28 size[x]=1; 29 Rep(i,x){ 30 int to=e[x][i]; 31 if(to==f[x]) continue; 32 dep[to]=dep[x]+1; 33 f[to]=x; 34 dfs(to); 35 if(!son[x]||size[to]>size[son[x]]) son[x]=to; 36 size[x]+=size[to]; 37 } 38 } 39 int Top; 40 void Dfs(int x){ 41 id[x]=++idcnt; 42 idr[id[x]]=x; 43 top[x]=Top; 44 if(son[x]) Dfs(son[x]); 45 Rep(i,x) if(!id[e[x][i]]) Dfs(Top=e[x][i]); 46 } 47 struct node{ 48 int l,r,sum,mx; 49 }; 50 node x[maxn<<2]; 51 void maintain(int k){ 52 x[k].sum=x[l(k)].sum+x[r(k)].sum; 53 x[k].mx=max(x[l(k)].mx,x[r(k)].mx); 54 } 55 void update(int k){ 56 if(x[k].l==x[k].r){ 57 x[k].sum=x[k].mx=v; 58 return; 59 } 60 int mid=(x[k].l+x[k].r)>>1; 61 update(u<=mid?l(k):r(k)); 62 maintain(k); 63 } 64 int findmx(int k,int l,int r){ 65 if(x[k].l==l&&x[k].r==r) return x[k].mx; 66 int mid=(x[k].l+x[k].r)>>1; 67 if(l>mid) return findmx(r(k),l,r); 68 if(r<=mid) return findmx(l(k),l,r); 69 return max(findmx(l(k),l,mid),findmx(r(k),mid+1,r)); 70 } 71 int findsum(int k,int l,int r){ 72 if(x[k].l==l&&x[k].r==r) return x[k].sum; 73 int mid=(x[k].l+x[k].r)>>1; 74 if(l>mid) return findsum(r(k),l,r); 75 if(r<=mid) return findsum(l(k),l,r); 76 return findsum(l(k),l,mid)+findsum(r(k),mid+1,r); 77 } 78 int askmx(){ 79 int ans=-inf; 80 while(top[u]!=top[v]){ 81 if(dep[top[u]]
dep[v]) swap(u,v); 86 ans=max(ans,findmx(1,id[u],id[v])); 87 return ans; 88 } 89 int asksum(){ 90 int ans=0; 91 while(top[u]!=top[v]){ 92 if(dep[top[u]] dep[v]) swap(u,v); 97 ans+=findsum(1,id[u],id[v]); 98 return ans; 99 }100 void build(int k,int l,int r){101 x[k].l=l,x[k].r=r;102 if(l==r){103 x[k].mx=x[k].sum=w[idr[l]];104 return;105 }106 int mid=(l+r)>>1;107 build(l(k),l,mid);108 build(r(k),mid+1,r);109 maintain(k);110 }111 void init(){112 dep[1]=0;113 dfs(1);Dfs(Top=1);114 build(1,1,n);115 }116 int main()117 { 118 n=read();119 rep(i,0,n-1){120 int from=read(),to=read();121 e[from].push_back(to);122 e[to].push_back(from);123 }124 rep(i,1,n+1) w[i]=read();125 init(); 126 m=read();127 while(m--){128 char c[10];129 scanf(" %s",c);130 u=read(),v=read();131 if(c[0]=='C'){132 u=id[u];133 update(1);134 }else if(c[1]=='M'){135 printf("%d\n",askmx());136 }else{137 printf("%d\n",asksum());138 }139 }140 return 0;141 } View Code 一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身
输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来1行，为一个整数q，表示操作的总数。接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。 对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。
对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。