@[xiaolou](/space/show?uid=68675) 您犯了一个很常见的错误。。第二遍dfs的时候，应该用
```cpp
dfs2(v,v);
```
而不是
```cpp
dfs2(v,u);
```
还有就是第二遍dfs初始部分应该用
```cpp
dfs2(r,r);
```
by NaCly_Fish @ 2019-05-09 19:06:04
第二遍dfs是划分重链的，一个轻儿子必定为一个重链的顶点
by NaCly_Fish @ 2019-05-09 19:07:20
@[NaCly_Fish](/space/show?uid=115864) 按您说的改了，然后样例Re了
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,R,k;
int a[100005];
struct Node
{
int v;
Node *next;
}*h[100005],pool[200005];
struct SGTree
{
int sum,la,le,ri;
}t[400005];
int top[100005];
int son[100005];
int size[100005];
int w[100005];
int rw[100005];
int dep[100005];
int f[100005];
int cnt=0,tot=0;
void Adde(int u,int v)
{
Node *p=&pool[++tot];
p->v=v;
p->next=h[u];
h[u]=p;
}
void Dfs1(int u,int fa)
{
int maxsize=-1,maxson=0;
size[u]=1;
f[u]=fa;
for(Node *p=h[u];p;p=p->next)
{
if(p->v!=fa)
{
dep[p->v]=dep[u]+1;
Dfs1(p->v,u);
if(maxsize<size[p->v])
{
maxsize=size[p->v];
maxson=p->v;
}
size[u]+=size[p->v];
}
}
son[u]=maxson;
}
void Dfs2(int u,int fa)
{
cnt++;
w[u]=cnt;
if(son[u])
{
top[son[u]]=top[u];
Dfs2(son[u],u);
}
for(Node *p=h[u];p;p=p->next)
{
if(p->v!=fa&&p->v!=son[u])
{
top[p->v]=p->v;
Dfs2(p->v,p->v);
}
}
}
void BuildT(int id,int l,int r)
{
t[id].le=l;
t[id].ri=r;
t[id].la=0;
if(t[id].le==t[id].ri)
{
t[id].sum=a[rw[t[id].le]]/*a[rw[t[id].ri]]*/;
return;
}
int M=(l+r)/2;
BuildT(id*2,l,M);
BuildT(id*2+1,M+1,r);
t[id].sum=t[id*2].sum+t[id*2+1].sum;
}
void Change(int id,int l,int r,int c)
{
if(t[id].le==l&&t[id].ri==r)
{
t[id].la+=c;
return;
}
if(t[id].la!=0)
{
t[id*2].la+=t[id].la;
t[id*2].la%=k;
t[id*2+1].la+=t[id].la;
t[id*2+1].la%=k;
t[id].la=0;
}
if(r<=t[id*2].ri)
{
Change(id*2,l,r,c);
}
else if(l>=t[id*2+1].le)
{
Change(id*2+1,l,r,c);
}
else
{
Change(id*2,l,t[id*2].ri,c);
Change(id*2+1,t[id*2+1].le,r,c);
}
t[id].sum=(t[id*2].sum%k+t[id*2].la*(t[id*2].ri-t[id*2].le+1)%k+t[id*2+1].sum%k+t[id*2+1].la*(t[id*2+1].ri-t[id*2+1].le+1)%k)%k;
}
int Query(int id,int l,int r)
{
if(t[id].le==l&&t[id].ri==r)
{
return (t[id].sum+t[id].la*(t[id].ri-t[id].le+1)%k)%k;
}
if(t[id].la)
{
t[id*2].la+=t[id].la;
t[id*2].la%=k;
t[id*2+1].la+=t[id].la;
t[id*2+1].la%=k;
t[id].sum+=t[id].la*(t[id].ri-t[id].le+1);
t[id].sum%=k;
t[id].la=0;
}
if(r<=t[id*2].ri)
{
return Query(id*2,l,r)%k;
}
else if(l>=t[id*2+1].le)
{
return Query(id*2+1,l,r)%k;
}
else
{
return (Query(id*2,l,t[id*2].ri)%k+Query(id*2+1,t[id*2+1].le,r)%k)%k;
}
}
int Ask(int x,int y)
{
int sum=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
{
swap(x,y);
}
sum+=Query(1,w[top[x]],w[x]);
sum%=k;
x=f[top[x]];
}
if(x!=y)
{
if(dep[x]>dep[y])
{
swap(x,y);
}
sum+=Query(1,w[x],w[y]);
sum%=k;
}
return sum%k;
}
void Modify(int x,int y,int z)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
{
swap(x,y);
}
Change(1,w[top[x]],w[x],z);
x=f[top[x]];
}
if(x!=y)
{
if(dep[x]>dep[y])
{
swap(x,y);
}
Change(1,w[x],w[y],z);
}
}
signed main()
{
scanf("%lld%lld%lld%lld",&n,&m,&R,&k);
for(int i=1;i<=n;++i)
{
scanf("%lld",&a[i]);
}
int uu,vv;
for(int i=1;i<n;++i)
{
scanf("%lld%lld",&uu,&vv);
Adde(uu,vv);
Adde(vv,uu);
}
Dfs1(R,0);
Dfs2(R,R);
for(int i=1;i<=n;++i)
{
if(!top[i])
{
top[i]=R;
}
}
for(int i=1;i<=n;++i)
{
rw[w[i]]=i;
}
int op,x,y,z;
BuildT(1,1,n);
for(int i=1;i<=m;++i)
{
scanf("%lld%lld",&op,&x);
if(op==1)
{
scanf("%lld%lld",&y,&z);
Modify(w[x],w[y],z);
}
else if(op==2)
{
scanf("%lld",&y);
printf("%lld\n",Ask(x,y));
}
else if(op==3)
{
scanf("%lld",&y);
Change(1,w[x],w[x]+size[x]-1,y);
}
else
{
printf("%lld\n",Query(1,w[x],w[x]+size[x]-1));
}
}
return 0;
}
```
by xiaolou @ 2019-05-09 19:11:22
@[xiaolou](/space/show?uid=68675) 您这个写法太神奇了，我改不来。。
by NaCly_Fish @ 2019-05-09 19:39:17
@[NaCly_Fish](/space/show?uid=115864) emmm，很神奇吗
by xiaolou @ 2019-05-09 19:42:52
@[xiaolou](/space/show?uid=68675) 可能只是我和您的码风差异比较大吧。。
强行安利一下我的树剖blog：[Link](https://www.luogu.org/blog/NaCly-Fish-blog/qwqQAQ)
by NaCly_Fish @ 2019-05-09 19:44:30
@[NaCly_Fish](/space/show?uid=115864) orz神鱼
by lsy263 @ 2019-07-11 23:57:50