如题，已知一棵包含 NN 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：
操作 11： 格式： 1\ x\ y\ z1 x y z 表示将树从 xx 到 yy 结点最短路径上所有节点的值都加上 zz。
操作 22： 格式： 2\ x\ y2 x y 表示求树从 xx 到 yy 结点最短路径上所有节点的值之和。
操作 33： 格式： 3\ x\ z3 x z 表示将以 xx 为根节点的子树内所有节点值都加上 zz。
操作 44： 格式： 4\ x4 x 表示求以 xx 为根节点的子树内所有节点值之和
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+100; typedef long long ll; int n,m,r,mod; vector<int> g[maxn]; int son[maxn];//重儿子编号 int id[maxn];//新编号 int fa[maxn];//父亲节点 int cnt; int dep[maxn]; int size[maxn];//子树大小 int top[maxn];//当前链顶节点 int w[maxn];//初始点权数组 int wt[maxn]; //线段树部分 struct node { int l,r; ll sum; ll lazy; }segTree[maxn*4]; void build (int i,int l,int r) { segTree[i].l=l; segTree[i].r=r; if (l==r) { segTree[i].sum=wt[l]; return; } int mid=(l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); segTree[i].sum=segTree[i<<1].sum+segTree[i<<1|1].sum; segTree[i].sum%=mod; } void spread (int i) { if (segTree[i].lazy) { segTree[i<<1].sum+=segTree[i].lazy*(segTree[i<<1].r-segTree[i<<1].l+1); segTree[i<<1].sum%=mod; segTree[i<<1|1].sum+=segTree[i].lazy*(segTree[i<<1|1].r-segTree[i<<1|1].l+1); segTree[i<<1].sum%=mod; segTree[i<<1].lazy+=segTree[i].lazy; segTree[i<<1|1].lazy+=segTree[i].lazy; segTree[i].lazy=0; } } void update (int i,int l,int r,int val) { //区间更新 if (l<=segTree[i].l&&segTree[i].r<=r) { segTree[i].sum+=(ll)val*(segTree[i].r-segTree[i].l+1); segTree[i].sum%=mod; segTree[i].lazy+=val; return; } spread(i); int mid=(segTree[i].l+segTree[i].r)>>1; if (l<=mid) update(i<<1,l,r,val); if (r>mid) update(i<<1|1,l,r,val); segTree[i].sum=segTree[i<<1].sum+segTree[i<<1|1].sum; segTree[i].sum%=mod; } ll query (int i,int l,int r) { if (l<=segTree[i].l&&r>=segTree[i].r) return segTree[i].sum%mod; spread(i); int mid=(segTree[i].l+segTree[i].r)>>1; ll ans=0; if (l<=mid) ans+=query(i<<1,l,r); if (r>mid) ans+=query(i<<1|1,l,r); return ans%mod; } //树剖部分 int qRange (int x,int y) { //查询路径权值和 int ans=0; while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); ans+=query(1,id[top[x]],id[x]); //加上x到x所在链的顶端这一段区间的点权和 ans%=mod; x=fa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点 } if (dep[x]>dep[y]) swap(x,y); ans+=query(1,id[x],id[y]); return ans%mod; } void upRange (int x,int y,int k) { //修改整条路径 k%=mod; while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); update(1,id[top[x]],id[x],k); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); update(1,id[x],id[y],k); } int qSon (int x) { //查询子树 return query(1,id[x],id[x]+size[x]-1); } int upSon (int x,int k) { //修改子树 update(1,id[x],id[x]+size[x]-1,k); } void dfs1 (int x,int f,int deep) { dep[x]=deep; fa[x]=f; size[x]=1; int maxson=-1;//记录重儿子的儿子数 for (int y:g[x]) { if (y==f) continue; dfs1(y,x,deep+1); size[x]+=size[y]; if (size[y]>maxson) son[x]=y,maxson=size[y]; } } void dfs2 (int x,int topf) { //topf表示当前链的最顶端的节点 id[x]=++cnt; wt[cnt]=w[x]; top[x]=topf; if (!son[x]) return; dfs2(son[x],topf);//先处理重儿子 for (int y:g[x]) { if (y==fa[x]||y==son[x]) continue; dfs2(y,y);//对于每个轻儿子都有一条属于它自己的链 } } int main () { scanf("%d%d%d%d",&n,&m,&r,&mod); for (int i=1;i<=n;i++) scanf("%d",w+i); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } dfs1(r,0,1); dfs2(r,r); build(1,1,n); while (m--) { int op; scanf("%d",&op); if (op==1) { int x,y,z; scanf("%d%d%d",&x,&y,&z); upRange(x,y,z); } else if (op==2) { int x,y; scanf("%d%d",&x,&y); printf("%d\n",qRange(x,y)); } else if (op==3) { int x,y; scanf("%d%d",&x,&y); upSon(x,y); } else { int x; scanf("%d",&x); printf("%d\n",qSon(x)); } } }
原文：https://www.cnblogs.com/zhanglichen/p/13420203.html