Problem Description wls 有三棵树，树上每个节点都有一个值 ai，现在有 2 种操作： 1, 将一条链上的所有节点的值开根号向下取整； 2 , 求一条链上值的和； 链的定义是两点之间的最短路。
Input 第一行两个数 n, q 分别代表树上点的数量和操作数量。 第二行 n 个整数，第 i 个数代表第 i 个点的值 ai。 接下来 n − 1 行， 每行两个整数 u, v 代表 u，v 之间有一条边。数据保证点两两联通。 接下来 q 行，每行有个整数 op, u, v，op = 0 表示将 u, v 这条链上所有的点的值开根号向下取整，op = 1表示询问 u，v 这条链上的值的和。 1 ≤ n, q ≤ 100, 000 0 ≤ ai ≤ 1, 000, 000, 000
Output 对于每一组 op = 2 的询问，输出一行一个值表示答案。
当时现场赛的时候一眼就看出来是个树剖，奈何没有学过树剖，照着板子敲了一会实在是懵逼。。。然后也没写出来。。。 起那两天重现赛把题放出来了，刚好也学了树剖，就补一下。 中间可以写一个剪枝，当这条路上所有的点权都为1的时候，就不用再继续开根号了，也就是e[root].sum==(e[root].r-e[root].l+1)的时候。 好像不剪枝也是可以过的。
#include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> using namespace std; const int N=1e5+7; int fi[N],tot; long long a[N]; int n,m,f[N],d[N],siz[N],son[N],rk[N],top[N],id[N],cnt; struct node { int v,nex; }; node edge[N*2]; struct Node { int l,r; long long sum; }; Node e[N*4]; void add(int u,int v) { edge[tot].v=v; edge[tot].nex=fi[u]; fi[u]=tot++; } void dfs1(int u) { siz[u]=1; d[u]=d[f[u]]+1; for(int i=fi[u];i!=-1;i=edge[i].nex) { int v=edge[i].v; if(v!=f[u]) { f[v]=u; dfs1(v); siz[u]+=siz[v]; if(siz[v]>siz[son[u]]) son[u]=v; } } } void dfs2(int u,int topp) { top[u]=topp; id[u]=++cnt; rk[cnt]=u; if(son[u]) dfs2(son[u],topp); for(int i=fi[u];i!=-1;i=edge[i].nex) { int v=edge[i].v; if(v!=f[u]&&v!=son[u]) dfs2(v,v); } } //线段树 void build(int root,int l,int r) { e[root].l=l; e[root].r=r; if(e[root].l==e[root].r) { e[root].sum=a[rk[l]]; return ; } else { build(root*2,l,(l+r)/2); build(root*2+1,(l+r)/2+1,r); e[root].sum=e[root*2].sum+e[root*2+1].sum; } } void update(int root,int l,int r) { if(e[root].sum==(e[root].r-e[root].l+1)) return ; if(e[root].l==e[root].r) { e[root].sum=(long long)sqrt(e[root].sum); return ; } else { int mid=(e[root].l+e[root].r)/2; if(l<=mid) update(root*2,l,r); if(r>mid) update(root*2+1,l,r); e[root].sum=e[root*2].sum+e[root*2+1].sum; } } void updates(int x,int y) { while(top[x]!=top[y]) { if(d[top[x]]<d[top[y]]) swap(x,y); update(1,id[top[x]],id[x]); x=f[top[x]]; } if(d[x]>d[y]) swap(x,y); update(1,id[x],id[y]); } long long que(int root,int l,int r) { if(e[root].l>=l&&e[root].r<=r) return e[root].sum; int mid=(e[root].l+e[root].r)/2; long long ans=0; if(l<=mid) ans+=que(root*2,l,r); if(r>mid) ans+=que(root*2+1,l,r); return ans; } long long ques(int x,int y) { long long ans=0; while(top[x]!=top[y]) { if(d[top[x]]<d[top[y]]) swap(x,y); ans+=que(1,id[top[x]],id[x]); x=f[top[x]]; } if(d[x]>d[y]) swap(x,y); ans+=que(1,id[x],id[y]); return ans; } int main() { memset(fi,-1,sizeof(fi)); scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); int x,y,z; for(int i=1;i<n;i++) { scanf("%d %d",&x,&y); add(x,y); add(y,x); } dfs1(1); dfs2(1,1); build(1,1,n); for(int i=1;i<=m;i++) { scanf("%d %d %d",&z,&x,&y); if(z==0) updates(x,y); else printf("%lld\n",ques(x,y)); } return 0; }