由于并不想造轮子，这里放上一位大佬的博客：link。这里只放我写的模板：
如果要处理边权，经典做法是将边权下放给所连两个点中深度更深的点。还有一种是在两点间塞入一个点，这个点称为”边点“，其点权代替边权。
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
typedef long long ll;
const ll N=100000+10,inf=214748364799999999;
#define lson (root*2)
#define rson ((root*2)+1)
#define mid ((l+r)/2)
ll n,m,Root,mod,a[N];
struct Seg_tree
{
struct node{ll data,tag;}t[N*4];
void pushup(ll root)
{
t[root].data=t[lson].data+t[rson].data%mod;
return;
}
void pushdown(ll root,ll l,ll r)
{
ll tag=t[root].tag%mod;
t[lson].data=(t[lson].data+(mid-l+1)*tag%mod)%mod;
t[rson].data=(t[rson].data+(r-mid)*tag%mod)%mod;
t[lson].tag=(t[lson].tag+tag)%mod;
t[rson].tag=(t[rson].tag+tag)%mod;
t[root].tag=0;
}
void build(ll root,ll l,ll r,ll d[])
{
if(l==r){t[root].data=d[l]%mod;return;}
build(lson,l,mid,d);
build(rson,mid+1,r,d);
pushup(root);
}
void update(ll root,ll l,ll r,ll x,ll y,ll data)
{
if(x<=l&&r<=y)
{
t[root].data+=(r-l+1)*data;
t[root].data%=mod;
t[root].tag+=data;
t[root].tag%=mod;
return;
}
pushdown(root,l,r);
if(x<=mid) update(lson,l,mid,x,y,data);
if(y>=mid+1) update(rson,mid+1,r,x,y,data);
pushup(root);
return;
}
ll query(ll root,ll l,ll r,ll x,ll y)
{
ll ret=0;
if(x<=l&&r<=y) return t[root].data%mod;
pushdown(root,l,r);
if(x<=mid) ret+=query(lson,l,mid,x,y);
if(y>=mid+1) ret+=query(rson,mid+1,r,x,y);
return ret%mod;
}
}SGT;
struct Graph
{
struct edge{ll nxt,to;}e[N*2];
ll cnt,head[N];
Graph(){memset(head,0,sizeof(head));cnt=0;}
void add(ll a,ll b)
{
e[++cnt]=(edge){head[a],b};
head[a]=cnt;
}
}tmp;
struct Tree
{
ll dad[N],dth[N],size[N],son[N];
ll num[N],data[N],top[N],cnt;
//父节点，深度，子树大小，重儿子。
//新编号，权值，链的顶端，编号分配 data。
Tree(){cnt=0;}
void dfs1(ll root,ll par,ll depth)
{
dth[root]=depth;
dad[root]=par;
size[root]=1;
ll sval=-1;
for(ll i=tmp.head[root];i;i=tmp.e[i].nxt)
{
ll to=tmp.e[i].to;
if(to==par) continue;
dfs1(to,root,depth+1);
size[root]+=size[to];
if(sval<size[to])
{
sval=size[to];
son[root]=to;
}
}
}
void dfs2(ll root,ll topn,ll val[])
{
num[root]=++cnt;
data[cnt]=val[root]%mod;
top[root]=topn;
if(!son[root]) return;
dfs2(son[root],topn,val);
for(ll i=tmp.head[root];i;i=tmp.e[i].nxt)
{
ll to=tmp.e[i].to;
if(to==dad[root]||to==son[root]) continue;
dfs2(to,to,val);
}
}
void init(ll val[])
{
dfs1(Root,0,1);
dfs2(Root,Root,val);
SGT.build(num[Root],1,n,data);
}
ll quyRange(ll x,ll y)
{
ll ans=0;
while(top[x]!=top[y])
{
if(dth[top[x]]<dth[top[y]]) swap(x,y);
ans=(ans+SGT.query(num[Root],1,n,num[top[x]],num[x]))%mod;
x=dad[top[x]];
}
if(dth[x]>dth[y]) swap(x,y);
ans=(ans+SGT.query(num[Root],1,n,num[x],num[y]))%mod;
return ans;
}
void updRange(ll x,ll y,ll val)
{
val%=mod;
while(top[x]!=top[y])
{
if(dth[top[x]]<dth[top[y]]) swap(x,y);
SGT.update(num[Root],1,n,num[top[x]],num[x],val);
x=dad[top[x]];
}
if(dth[x]>dth[y]) swap(x,y);
SGT.update(num[Root],1,n,num[x],num[y],val);
}
ll quyTree(ll x){return SGT.query(num[Root],1,n,num[x],num[x]+size[x]-1)%mod;}
void updTree(ll x,ll val){SGT.update(num[Root],1,n,num[x],num[x]+size[x]-1,val);}
}tree;
void main()
{
ll x,y,opt,val;
scanf("%lld%lld%lld%lld",&n,&m,&Root,&mod);
for(ll i=1;i<=n;i++) scanf("%lld",a+i);
for(ll i=1;i<=n-1;i++)
{
scanf("%lld%lld",&x,&y);
tmp.add(x,y);
tmp.add(y,x);
}
tree.init(a);
for(ll i=1;i<=m;i++)
{
scanf("%lld",&opt);
if(opt==1)
{
scanf("%lld%lld%lld",&x,&y,&val);
tree.updRange(x,y,val);
}
else if(opt==2)
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",tree.quyRange(x,y)%mod);
}
else if(opt==3)
{
scanf("%lld%lld",&x,&val);
tree.updTree(x,val);
}
else
{
scanf("%lld",&x);
printf("%lld\n",tree.quyTree(x)%mod);
}
}
return;
}
}
int main()
{
_yz::main();
return 0;
}
例题：
- P3178 [HAOI2015]树上操作
- P1505 [国家集训队]旅游
- P4315 月下“毛景树”
本文作者：Yurchiu
本文链接：https://yz-hs.github.io/fc571536ccbb/
版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。
