Tree

wls 有三棵树，树上每个节点都有一个值 aiai，现在有 2 种操作：  1. 将一条链上的所有节点的值开根号向下取整；  2. 求一条链上值的和；  链的定义是两点之间的最短路。

Input

第一行两个数 nn, qq 分别代表树上点的数量和操作数量。  第二行 nn 个整数，第 ii 个数代表第 ii 个点的值 aiai。  接下来 nn −− 11 行， 每行两个整数 uu, vv 代表 uu，vv 之间有一条边。数据保证点两两联通。  接下来 qq 行，每行有个整数 opop, uu, vv，opop = 0 表示将 uu, vv 这条链上所有的点的值开根号向下取整，opop = 1表示询问 uu，vv 这条链上的值的和。  1 ≤ nn, qq ≤ 100, 000  0 ≤ aiai ≤ 1, 000, 000, 000

Output

对于每一组 opop = 2 的询问，输出一行一个值表示答案。

Sample Input

4 4 2 3 4 5 1 2 2 3 2 4 0 3 4 0 1 3 1 2 3 1 1 4

Sample Output

2 4

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6547

思路：树链剖分把树分成多条链，线段树维护区间和，实现区间开根号 区间求和

代码：

#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define ll long long const int N=100005; int n,m,tot,cnt; int first[N]; ll sum[N<<2],w[N],wt[N]; int d[N],fa[N],siz[N],son[N],top[N],id[N],rk[N]; struct node { int v,nex; }e[N<<1]; void adde(int u,int v) { e[tot].v=v; e[tot].nex=first[u]; first[u]=tot++; } void init() { tot=cnt=0; memset(first,-1,sizeof(first)); memset(son,0,sizeof(son)); } void dfs1(int u,int pre,int depth) //处理 d,fa,siz,son 数组 { d[u]=depth; fa[u]=pre; siz[u]=1; for(int i=first[u];~i;i=e[i].nex) { int v=e[i].v; if(v==pre) continue; dfs1(v,u,depth+1); siz[u]+=siz[v]; if(siz[v]>siz[son[u]]) son[u]=v; } } void dfs2(int u,int t) //处理 top id rk wt 数组 { top[u]=t; id[u]=++cnt; rk[cnt]=u; wt[cnt]=w[u]; if(!son[u]) return; dfs2(son[u],t); for(int i=first[u];~i;i=e[i].nex) { int v=e[i].v; if(v!=son[u]&&v!=fa[u]) dfs2(v,v); } } void pushup(int rt) { sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void build(int l,int r,int rt) //建线段树 { if(l==r) { sum[rt]=wt[l]; return; } int mid=(l+r)>>1; build(lson); build(rson); pushup(rt); } void update(int L,int R,int l,int r,int rt) //[L,R]区间开根号 { if(sum[rt]==r-l+1) return; //区间内所有点都为1，就不用再往下更新了 if(l==r) { sum[rt]=(ll)sqrt(sum[rt]); return; } int mid=(l+r)>>1; if(L<=mid) update(L,R,lson); if(mid<R) update(L,R,rson); pushup(rt); } ll query(int L,int R,int l,int r,int rt) // 查询[L,R]区间的和 { if(L<=l&&r<=R) return sum[rt]; int mid=(l+r)>>1; ll ans=0; if(L<=mid) ans+=query(L,R,lson); if(mid<R) ans+=query(L,R,rson); return ans; } void uprange(int x,int y) //x到y的最短路径开根 { while(top[x]!=top[y]) { if(d[top[x]]<d[top[y]]) swap(x,y); update(id[top[x]],id[x],1,n,1); x=fa[top[x]]; } if(d[x]>d[y]) swap(x,y); update(id[x],id[y],1,n,1); } ll querange(int x,int y) //求x到y的最短路径的和 { ll ans=0; while(top[x]!=top[y]) { if(d[top[x]]<d[top[y]]) swap(x,y); ans+=query(id[top[x]],id[x],1,n,1); x=fa[top[x]]; } if(d[x]>d[y]) swap(x,y); ans+=query(id[x],id[y],1,n,1); return ans; } int main() { scanf("%d%d",&n,&m); init(); for(int i=1;i<=n;i++) scanf("%lld",&w[i]); int u,v; for(int i=1;i<n;i++) //存原树 { scanf("%d%d",&u,&v); adde(u,v); adde(v,u); } dfs1(1,0,1); dfs2(1,1); build(1,n,1); int op,x,y; while(m--) { scanf("%d%d%d",&op,&x,&y); if(op==0) uprange(x,y); else if(op==1) printf("%lld\n",querange(x,y)); } return 0; }