简单题，看题目就懂。
#include<queue> #include<stack> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define INF 99999999 #define ll __int64 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; const int MAXN = 30010; struct node { int to; int v; int next; }edge[MAXN*3]; int pre[MAXN],ind,top[MAXN],fa[MAXN],son[MAXN],w[MAXN],deq[MAXN],siz[MAXN],fn; int tree[MAXN<<2],val[MAXN],n; void add(int x,int y) { edge[ind].to = y; edge[ind].next = pre[x]; pre[x] = ind++; } //第一次搜索找出siz[],son[],deq[],fa[] void dfs1(int rt,int pa,int d) { deq[rt] = d; son[rt] = 0; fa[rt] = pa; siz[rt] = 1; int i; for(i=pre[rt]; i!=-1; i=edge[i].next){ int t = edge[i].to; if(t != fa[rt]){ dfs1(t,rt,d+1); siz[rt] += siz[t]; if(siz[son[rt]] < siz[t]){//如果父节点的son[rt]的iz[]小于子节点的siz[]更新son[] son[rt] = t; } } } } //第二次搜索找到w[],top[] void dfs2(int rt,int tp) { top[rt] = tp; w[rt] = ++fn; if(son[rt] != 0) dfs2(son[rt],tp);//如果当前父节点纯在son 那么为了让链在线段树中连续 先对son[]进行搜索，并且重边顶端的点相同。 for(int i=pre[rt]; i!=-1; i=edge[i].next){ int t = edge[i].to; if(t != fa[rt] && son[rt] != t){ dfs2(t,t); } } } /******************************/ void pushup(int rt) { tree[rt] = tree[rt<<1]+tree[rt<<1|1]; } void Insert(int p,int v,int l,int r,int rt) { if(l == r){ tree[rt] = v; return ; } int m = (l+r)/2; if(m >= p){ Insert(p,v,lson); } else{ Insert(p,v,rson); } pushup(rt); } void updata(int p,int v,int l,int r,int rt) { if(l == r){ tree[rt] = v; return ; } int m = (l+r)/2; if(m >= p){ updata(p,v,lson); } else { updata(p,v,rson); } pushup(rt); } int query(int L,int R,int l,int r,int rt) { if(L<=l && r<=R){ return tree[rt]; } int m = (l+r)/2; int ans = 0; if(m >= L){ ans += query(L,R,lson); } if(m < R){ ans += query(L,R,rson); } return ans; } int lca(int x,int y) { int ans = 0; while(top[x] != top[y]) { if(deq[top[x]] < deq[top[y]]){ swap(x,y); } ans += query(w[top[x]],w[x],1,fn,1); x = fa[top[x]]; } //注意线段和点之间的差别 if(deq[x] < deq[y]){ swap(x,y); } return ans+query(w[y],w[x],1,fn,1); } int main() { int i,j,t,ff = 0; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1; i<=n; i++){ scanf("%d",&val[i]); } ind = 1; memset(pre,-1,sizeof(pre)); for(i=1; i<n; i++){ int x,y; scanf("%d%d",&x,&y); add(x+1,y+1); add(y+1,x+1); } memset(tree,0,sizeof(tree)); dfs1(1,1,1); fn = 0; dfs2(1,1); for(i=1; i<=n; i++){ Insert(w[i],val[i],1,fn,1); } int ft; scanf("%d",&ft); printf("Case %d: ",++ff); while(ft--) { int flag; scanf("%d",&flag); if(flag == 1){ int x,y; scanf("%d%d",&x,&y); x++; updata(w[x],y,1,fn,1); } else { int x,y; scanf("%d%d",&x,&y); x++; y++; printf("%d ",lca(x,y)); } } } }