本文共 4642 字，大约阅读时间需要 15 分钟。
题目描述
如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：
操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z
操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和
操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z
操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和
输入格式
第一行包含4个正整数N、M、R、P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。
接下来一行包含N个非负整数，分别依次表示各个节点上初始的数值。
接下来N-1行每行包含两个整数x、y，表示点x和点y之间连有一条边（保证无环且连通）
接下来M行每行包含若干个正整数，每行表示一个操作，格式如下：
操作1： 1 x y z
操作2： 2 x y
操作3： 3 x z
操作4： 4 x
输出格式
输出包含若干行，分别依次表示每个操作2或操作4所得的结果（对P取模）
输入输出样例
输入 #1
5 5 2 24
7 3 7 8 0
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3
输出 #1
2
21
说明/提示
时空限制：1s，128M
数据规模：
对于100%的数据：n<=1e5,m<=1e5
思路:
基于点权的树链剖分模板
操作流程：
第一次dfs求sz[x],fa[x],son[x],d[x]，求出轻重儿子用于下一步dfs
第二次dfs求top[x],id[x],rk[x]，定向dfs记录序号，用于下一步dfs序建线段树
后面就是建树，操作
实质上是定向dfs序建立线段树，暴力处理路径问题，dfs序也可以用于处理子树问题。
//
支持单点修改，子树修改，路径求和，路径求改等
因为有区间加法所以用的是线段树
而不是树状数组(树状数组区间操作很麻烦)
代码有注释
ps:
挂两种代码：
一种非动态开点，数组要开4倍maxm
一种动态开点，数组只需要2倍maxm，比较小
code1:
//非动态开点
//p3384#include #include #include using namespace std;const int maxm=1e5+5;const int M=maxm<<1;int head[maxm],nt[M],to[M],cnt;int sz[maxm];int son[maxm];int d[maxm];int fa[maxm];int top[maxm];int id[maxm];int rk[maxm];int v[maxm];int n,m,root,mod;struct Node{ int l,r,sum,lz;}a[maxm<<2];void init(){ //init memset(head,-1,sizeof head); cnt=1;}void add(int x,int y){ //add cnt++;nt[cnt]=head[x];head[x]=cnt;to[cnt]=y;}void dfs1(int x){ //sz[x],fa[x],son[x],d[x]; sz[x]=1; d[x]=d[fa[x]]+1; son[x]=0; for(int i=head[x];i!=-1;i=nt[i]){ int v=to[i]; if(v==fa[x])continue; fa[v]=x; dfs1(v); sz[x]+=sz[v]; if(sz[son[x]] =r){ (a[node].sum+=len(node)*val)%=mod; (a[node].lz+=val)%=mod; return ; } pushdown(node); int mid=(l+r)/2; if(st<=mid){ update(st,ed,val,node*2); } if(ed>=mid+1){ update(st,ed,val,node*2+1); } pushup(node);}int ask(int st,int ed,int node){ //区间求和 int l=a[node].l,r=a[node].r; if(st<=l&&ed>=r){ return a[node].sum; } pushdown(node); int mid=(l+r)/2; int ans=0; if(st<=mid){ (ans+=ask(st,ed,node*2))%=mod; } if(ed>=mid+1){ (ans+=ask(st,ed,node*2+1))%=mod; } return ans;}void roadadd(int x,int y,int z){ //路径加法 while(top[x]!=top[y]){ if(d[top[x]] id[y]){ //改dfs序小的为x,否则区间加法死循环 swap(x,y); } update(id[x],id[y],z,1);}int roadask(int x,int y){ //路径求和 int ans=0; while(top[x]!=top[y]){ if(d[top[x]] id[y]){ //改dfs序小的为x,否则区间查询死循环 swap(x,y); } (ans+=ask(id[x],id[y],1))%=mod; return ans;}signed main(){ init(); scanf("%d%d%d%d",&n,&m,&root,&mod); for(int i=1;i<=n;i++){ scanf("%d",&v[i]); } for(int i=1;i
code2:
//动态开点
//p3384#include #include #include using namespace std;const int maxm=1e5+5;const int M=maxm<<1;int head[maxm],nt[M],to[M],cnt;int sz[maxm];int son[maxm];int d[maxm];int fa[maxm];int top[maxm];int id[maxm];int rk[maxm];int v[maxm];int n,m,root,mod;struct Node{ int l,r,lc,rc,sum,lz;}a[maxm<<1];void init(){ //init memset(head,-1,sizeof head); cnt=1; sz[0]=0;}void add(int x,int y){ //add cnt++;nt[cnt]=head[x];head[x]=cnt;to[cnt]=y;}void dfs1(int x){ //sz[x],fa[x],son[x],d[x]; sz[x]=1; d[x]=d[fa[x]]+1; son[x]=0; for(int i=head[x];i!=-1;i=nt[i]){ int v=to[i]; if(v==fa[x])continue; fa[v]=x; dfs1(v); sz[x]+=sz[v]; if(sz[son[x]] =r){ (a[node].sum+=len(node)*val)%=mod; (a[node].lz+=val)%=mod; return ; } pushdown(node); int mid=(l+r)/2; if(st<=mid){ update(st,ed,val,a[node].lc); } if(ed>=mid+1){ update(st,ed,val,a[node].rc); } pushup(node);}int ask(int st,int ed,int node){ //区间求和 int l=a[node].l,r=a[node].r; if(st<=l&&ed>=r){ return a[node].sum; } pushdown(node); int mid=(l+r)/2; int ans=0; if(st<=mid){ (ans+=ask(st,ed,a[node].lc))%=mod; } if(ed>=mid+1){ (ans+=ask(st,ed,a[node].rc))%=mod; } return ans;}void roadadd(int x,int y,int z){ //路径加法 while(top[x]!=top[y]){ if(d[top[x]] id[y]){ //改dfs序小的为x,否则区间加法死循环 swap(x,y); } update(id[x],id[y],z,root);}int roadask(int x,int y){ //路径求和 int ans=0; while(top[x]!=top[y]){ if(d[top[x]] id[y]){ //改dfs序小的为x,否则区间查询死循环 swap(x,y); } (ans+=ask(id[x],id[y],root))%=mod; return ans;}signed main(){ init(); scanf("%d%d%d%d",&n,&m,&root,&mod); for(int i=1;i<=n;i++){ scanf("%d",&v[i]); } for(int i=1;i
转载地址：http://cnzv.baihongyu.com/