```cpp
int main()
{
cin>>n>>m>>root>>mod;
for(int i=1;i<=n;i++)
{
cin>>val[i];
}
for(int i=1;i<=n-1;i++)
{
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs1(root,0,1);
dfs2(root,root);
//puts("adsdas");
while(m--)
{
int op;
cin>>op;
if(op==1)//操作一
{
int x,y,k;
cin>>x>>y>>k;
upRange(x,y,k);
}
if(op==2)
{
int x,y;
res=0;
cin>>x>>y;
cout<<queryRange(x,y)<<endl;
}
if(op==3)
{
int x,k;
cin>>x>>k;
upson(x,k);
}
if(op==4)
{
int x;
cin>>x;
cout<<queryson(x)<<endl;
}
}
return 0;
//system("pause");
}
```
by Miss_dijkstra @ 2019-05-26 12:05:38
为什么我感觉你的代码很长。
就是史诗级工业题的那种感觉。
by redegg @ 2019-05-26 13:37:04
@[redegg](/space/show?uid=34663) ~~猪国杀~~
by Miss_dijkstra @ 2019-05-26 14:05:34
@[托儿索](/space/show?uid=107689)
为什么我的树剖和你的不太一样？
```cpp
#include <bits/stdc++.h>
#define int LL
#define lowbit(i) ((i)&(-(i)))
using namespace std;
typedef long long LL;
const int MAX_N=100005;
int n,m,root,Mod;
vector <int> g[MAX_N];
int bel[MAX_N];
int siz[MAX_N];
int depth[MAX_N];
int A[MAX_N];
int A_[MAX_N];
int sum[MAX_N];
int dfn[MAX_N];
int Index;
int f[MAX_N][21];
int dfs_(int v,int fa)
{
f[v][0]=fa;
depth[v]=depth[fa]+1;
siz[v]=1;
for(int i=0;i<(int)g[v].size();i++)
{
int u=g[v][i];
if(u==fa)continue;
siz[v]+=dfs_(u,v);
}
return siz[v];
}
void dfs(int v,int chain)
{
dfn[v]=++Index;
bel[v]=chain;
int k=0;
for(int i=0;i<(int)g[v].size();i++)
{
int u=g[v][i];
if(depth[u]==depth[v]+1 && siz[u]>siz[k])k=u;
}
if(k)dfs(k,chain);
for(int i=0;i<(int)g[v].size();i++)
{
int u=g[v][i];
if(depth[u]==depth[v]+1 && u!=k)dfs(u,u);
}
}
struct BIT
{
int d1[MAX_N];
int d2[MAX_N];
void add(int *arr,int i,int x)
{
while(i<=n)
{
arr[i]+=x;
arr[i]%=Mod;
i+=lowbit(i);
}
}
void modify(int l,int r,int x)
{
add(d1,l,x);
add(d1,r+1,-x);
add(d2,l,x*l);
add(d2,r+1,-x*(r+1));
}
int get_sum(int *arr,int i)
{
int res=0;
while(i>0)
{
res+=arr[i];
res%=Mod;
i-=lowbit(i);
}
return res;
}
int pre_sum(int i)
{
return (sum[i]+(i+1)*get_sum(d1,i)-get_sum(d2,i))%Mod;
}
int query(int l,int r)
{
return pre_sum(r)-pre_sum(l-1);
}
}bit;
int lca(int u,int v)
{
if(depth[u]<depth[v])swap(u,v);
int t=depth[u]-depth[v];
for(int j=20;j>=0;j--)
{
if(t&(1<<j))u=f[u][j];
}
if(u==v)return v;
for(int j=20;j>=0;j--)
{
if(f[u][j]!=f[v][j])
{
u=f[u][j];
v=f[v][j];
}
}
return f[u][0];
}
signed main()
{
cin>>n>>m>>root>>Mod;
for(int i=1;i<=n;i++)
{
cin>>A[i];
}
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs_(root,0);
dfs(root,root);
for(int j=1;j<=20;j++)
{
for(int i=1;i<=n;i++)
{
f[i][j]=f[f[i][j-1]][j-1];
}
}
for(int i=1;i<=n;i++)
{
A_[dfn[i]]=A[i];
}
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+A_[i];
sum[i]%=Mod;
}
while(m--)
{
int opt;
cin>>opt;
// cout<<"opt "<<opt<<":";
if(opt==1)
{
int u,v,w;
cin>>u>>v>>w;
int t=lca(u,v);
while(bel[u]!=bel[t])
{
bit.modify(dfn[bel[u]],dfn[u],w);
u=f[bel[u]][0];
}
bit.modify(dfn[t],dfn[u],w);
while(bel[v]!=bel[t])
{
bit.modify(dfn[bel[v]],dfn[v],w);
v=f[bel[v]][0];
}
bit.modify(dfn[t],dfn[v],w);
bit.modify(dfn[t],dfn[t],-w);
}
else if(opt==2)
{
int u,v;
cin>>u>>v;
int t=lca(u,v);
int ans=0;
while(bel[u]!=bel[t])
{
ans+=bit.query(dfn[bel[u]],dfn[u]);
ans%=Mod;
u=f[bel[u]][0];
}
ans+=bit.query(dfn[t],dfn[u]);
while(bel[v]!=bel[t])
{
ans+=bit.query(dfn[bel[v]],dfn[v]);
ans%=Mod;
v=f[bel[v]][0];
}
ans+=bit.query(dfn[t],dfn[v]);
ans-=bit.query(dfn[t],dfn[t]);
ans%=Mod;
if(ans<0)ans+=Mod;
cout<<ans<<endl;
}
else if(opt==3)
{
int v,w;
cin>>v>>w;
bit.modify(dfn[v],dfn[v]+siz[v]-1,w);
}
else
{
int v;
cin>>v;
int ans=bit.query(dfn[v],dfn[v]+siz[v]-1);
ans%=Mod;
if(ans<0)ans+=Mod;
cout<<ans<<endl;
}
}
return 0;
}
```
by Smile_Cindy @ 2019-05-26 14:09:03
@[Alpha](/space/show?uid=87058) 不知道也许是我比较特殊
by Miss_dijkstra @ 2019-05-26 14:34:38
在线%机房dalao
by foxdemon @ 2019-05-26 19:04:25