题目链接：传送门
题目大意：一棵无根树，每个点上有权值，两种操作，0 x y询问x~y路径上权值和 1 x y将
节点 x 权值变为y。对于询问操作输出答案。
题目思路：树链剖分
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <algorithm> 6 #include <cstring> 7 #include <stack> 8 #include <cctype> 9 #include <queue> 10 #include <string> 11 #include <vector> 12 #include <set> 13 #include <map> 14 #include <climits> 15 #define lson rt<<1,l,mid 16 #define rson rt<<1|1,mid+1,r 17 #define fi first 18 #define se second 19 #define ping(x,y) ((x-y)*(x-y)) 20 #define mst(x,y) memset(x,y,sizeof(x)) 21 #define mcp(x,y) memcpy(x,y,sizeof(y)) 22 using namespace std; 23 #define gamma 0.5772156649015328606065120 24 #define MOD 1000000007 25 #define inf 0x3f3f3f3f 26 #define N 30005 27 #define maxn 30010 28 typedef pair<int,int> PII; 29 typedef long long LL; 30 LL read(){ 31 LL x=0,f=1;char ch=getchar(); 32 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 33 while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} 34 return x*f; 35 } 36 37 int n,m,k,v,head[N],a[N],hcnt,L,R; 38 struct Edge{int to,nxt;}node[N<<1]; 39 int son[N],siz[N],id[N],tid; 40 int fa[N],top[N],dep[N],posi[N]; 41 LL seg[N<<2]; 42 void init(){ 43 mst(head,-1);mst(id,0);mst(siz,0); 44 mst(son,0);hcnt=tid=0; 45 } 46 void dfs1(int u,int f,int deep){ 47 fa[u]=f,dep[u]=deep,siz[u]=1; 48 for(int i=head[u];~i;i=node[i].nxt){ 49 int e=node[i].to;if(e==f)continue; 50 dfs1(e,u,deep+1);siz[u]+=siz[e]; 51 if(!son[u]||siz[son[u]]<siz[e])son[u]=e; 52 } 53 } 54 void dfs2(int u,int tp){ 55 top[u]=tp,id[u]=++tid,posi[tid]=u; 56 if(!son[u])return;dfs2(son[u],tp); 57 for(int i=head[u];~i;i=node[i].nxt){ 58 int e=node[i].to; 59 if(!id[e])dfs2(e,e); 60 } 61 } 62 void build(int rt,int l,int r){ 63 if(l==r){seg[rt]=a[posi[l]];return;} 64 int mid=l+r>>1; 65 build(lson);build(rson); 66 seg[rt]=seg[rt<<1]+seg[rt<<1|1]; 67 } 68 void update(int rt,int l,int r){ 69 if(l==r){seg[rt]=v;return;} 70 int mid=l+r>>1; 71 if(L<=mid)update(lson); 72 else update(rson); 73 seg[rt]=seg[rt<<1]+seg[rt<<1|1]; 74 } 75 LL query(int rt,int l,int r){ 76 if(L<=l&&r<=R)return seg[rt]; 77 int mid=l+r>>1;LL temp=0; 78 if(L<=mid)temp+=query(lson); 79 if(R>mid) temp+=query(rson); 80 return temp; 81 } 82 void lca(int x,int y){ 83 LL res=0; 84 while(top[x]!=top[y]){ 85 if(dep[top[x]]<dep[top[y]])swap(x,y); 86 L=id[top[x]],R=id[x]; 87 res+=query(1,1,n); 88 x=fa[top[x]]; 89 } 90 if(dep[x]<dep[y])swap(x,y); 91 L=id[y],R=id[x]; 92 res+=query(1,1,n); 93 printf("%lld ",res); 94 } 95 int main(){ 96 int i,j,group,x,y,Case=0; 97 group=read(); 98 while(group--){ 99 init(); 100 n=read(); 101 for(i=1;i<=n;++i)a[i]=read(); 102 for(i=1;i<n;++i){ 103 x=read(),y=read(); 104 ++x;++y; 105 node[hcnt].to=y,node[hcnt].nxt=head[x],head[x]=hcnt++; 106 node[hcnt].to=x,node[hcnt].nxt=head[y],head[y]=hcnt++; 107 } 108 dfs1(1,1,1);dfs2(1,1);build(1,1,n); 109 m=read(); 110 printf("Case %d: ",++Case); 111 while(m--){ 112 x=read(); 113 if(!x){ 114 x=read(),y=read(); 115 ++x;++y; 116 lca(x,y); 117 } 118 else{ 119 x=read(),y=read(); 120 ++x; 121 L=id[x],v=y; 122 update(1,1,n); 123 } 124 } 125 } 126 return 0; 127 }