或许我应该@[树链剖分](/space/show?uid=124721) ？
by 引领天下 @ 2019-07-13 16:49:26
@[引领天下](/space/show?uid=39863) 你为什么`query`和`chge`为什么要写`tree.ask(r,...)`之类的东西啊……
by F1aMiR3 @ 2019-07-13 17:01:10
~~同问。~~
by nosta @ 2019-07-13 17:02:54
~~宁的线段树似乎是建在点的原编号上而不是dfs序上的~~
by kma_093 @ 2019-07-13 17:04:46
还有宁的dfs2是不是手癌了
```
if (to[i]==fa[i]||to[i]==son[i])continue;
```
应该是
```
if (to[i]==fa[x]||to[i]==son[x])continue;
```
by kma_093 @ 2019-07-13 17:14:42
```
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
#define ll long long
int dep[N],siz[N],fa[N],z[N],to[N<<1],beg[N<<1],nxt[N<<1],top[N<<2],bian,son[N<<1],id[N<<1],tot,n,m,r,mod,num[N];
struct Tree{
ll ans[N<<2],tag[N<<2],a[N];
inline ll lson(ll p){return p<<1;}
inline ll rson(ll p){return (p<<1)|1;}
inline void push_up(ll p){ans[p]=(ans[lson(p)]+ans[rson(p)])%mod;}
inline void build(ll p,ll l,ll r){
if (l==r){ans[p]=a[num[l]];return ;}
ll mid=(l+r)>>1;
build(lson(p),l,mid);
build(rson(p),mid+1,r);
push_up(p);
tag[p]=0;
}
inline void lazy_tag(ll p,ll l,ll r,ll k){ans[p]=(ans[p]+(r-l+1)*k)%mod,tag[p]=(tag[p]+k)%mod;}
inline void push_down(ll p,ll l,ll r){
ll mid=(l+r)>>1;
lazy_tag(lson(p),l,mid,tag[p]);
lazy_tag(rson(p),mid+1,r,tag[p]);
tag[p]=0;
}
inline void change(ll p,ll nl,ll nr,ll l,ll r,ll k){//nl,nr->changing l,changing r;l,r->visiting l,visiting r
if (nl<=l&&nr>=r){ans[p]=(ans[p]+(r-l+1)*k)%mod,tag[p]=(tag[p]+k)%mod;return;}
ll mid=(l+r)>>1;
push_down(p,l,r);
if (nl<=mid)change(lson(p),nl,nr,l,mid,k);
if (nr>mid)change(rson(p),nl,nr,mid+1,r,k);
push_up(p);
}
inline ll ask(ll p,ll nl,ll nr,ll l,ll r){
if (nl<=l&&nr>=r)return ans[p];
ll mid=(l+r)>>1,res=0;
push_down(p,l,r);
if (nl<=mid)res=(res+ask(lson(p),nl,nr,l,mid))%mod;
if (nr>mid)res=(res+ask(rson(p),nl,nr,mid+1,r))%mod;
return res;
}
}tree;
inline void add(int u,int v){
to[++bian]=v;
nxt[bian]=beg[u];
beg[u]=bian;
}
inline void dfs1(int x){
siz[x]=1;
for (int i=beg[x];i;i=nxt[i]){
if (to[i]==fa[x])continue;
fa[to[i]]=x;
dep[to[i]]=dep[x]+1;
dfs1(to[i]);
siz[x]+=siz[to[i]];
if (siz[to[i]]>siz[son[x]])son[x]=to[i];
}
}
inline void dfs2(int x,int y){
top[x]=y;id[x]=++tot;num[tot] = x;
if (son[x])dfs2(son[x],y);
for (int i=beg[x];i;i=nxt[i]){
if (to[i]==fa[x]||to[i]==son[x])continue;
dfs2(to[i],to[i]);
}
}
int query(int x,int y){
int ans=0;
while (top[x]!=top[y]){
if (dep[top[x]]<dep[top[y]])swap(x,y);
ans=(ans+tree.ask(1,id[top[x]],id[x],1,n))%mod;
x=fa[top[x]];
}
if (dep[x]<dep[y])swap(x,y);
ans=(ans+tree.ask(1,id[y],id[x],1,n))%mod;
return ans;
}
void chge(int x,int y,int k){
k%=mod;
while (top[x]!=top[y]){
if (dep[top[x]]<dep[top[y]])swap(x,y);
tree.change(1,id[top[x]],id[x],1,n,k);
x=fa[top[x]];
}
if (dep[x]<dep[y])swap(x,y);
tree.change(1,id[y],id[x],1,n,k);
}
signed main(){
scanf ("%lld%lld%lld%lld",&n,&m,&r,&mod);fa[r]=0,dep[r]=1;
for (int i=1;i<=n;i++)scanf ("%lld",&tree.a[i]);
for (int i=1;i<n;i++){
int a,b;
scanf("%lld%lld",&a,&b);
add(a,b),add(b,a);
}
dfs1(r);
dfs2(r,r);
tree.build(1,1,n);
while(m--){
int flag,x,y,k;
scanf ("%lld",&flag);
switch (flag){
case 1:scanf ("%lld%lld%lld",&x,&y,&k);chge(x,y,k);break;
case 2:scanf ("%lld%lld",&x,&y);printf("%lld\n",query(x,y));break;
case 3:scanf ("%lld%lld",&x,&k);tree.change(1,id[x],id[x]+siz[x]-1,1,n,k);break;
case 4:scanf ("%lld",&x);printf("%lld\n",tree.ask(1,id[x],id[x]+siz[x]-1,1,n));
}
}
}
```
这份应该能[A](https://www.luogu.org/recordnew/show/20744590)了，里面大概有几个问题
- 宁好像总是把线段树的root = 1和原树的r搞混了，在链加和链查询函数里面（或者可能其他地方也有）
- 好像有个地方宁的
```res = (res + ...) % mod```
写成了```res = (...)%mod```
别的并不知道还有没有，上边那份是蒟蒻在宁的代码上进行了一番魔改的结果_(:з」∠)_宁可以两份对着查一查
~~不说了去打游戏了~~
by kma_093 @ 2019-07-13 17:30:31
@[kma_093](/space/show?uid=43515) r和1混淆是不存在的……只是手癌晚期而已
反正谢谢大佬orz
by 引领天下 @ 2019-07-13 21:49:22
@[Aiming_High](/space/show?uid=87393) @[nosta](/space/show?uid=125139) 怕线段树出锅，所以就直接使用我之前封装的了
by 引领天下 @ 2019-07-13 22:13:52