@[Fractures](/space/show?uid=78791)
dfs1里是不是size忘赋初值1了qwq
by Ynoi @ 2019-08-03 08:38:00
你应该先dfs再build建树
by ZYF_B @ 2019-08-03 08:38:39
而且build中的a[l]应该改成a[rnk[l]]
by ZYF_B @ 2019-08-03 08:43:42
楼上大佬说的都对
by Frozencode @ 2019-08-03 08:43:47
@[树链剖分](/space/show?uid=124721)
改了之后为什么输出出问题了
```cpp
#include<cstdio>
#include<iomanip>
#define ll long long
using std::max;
using std::swap;
const int MAXN=100001;
int n,m,r,p;
ll a[MAXN],tag[MAXN<<2],ans[MAXN<<2];
ll to[MAXN],next[MAXN],head[MAXN];
inline void add(int a,int b){
static int ccnt=0;
ccnt++;
next[ccnt]=head[a];
head[a]=ccnt;
to[ccnt]=b;
}
ll father[MAXN],son[MAXN],top[MAXN],depth[MAXN],size[MAXN],tid[MAXN],rnk[MAXN];
void dfs1(int u,int fa){
father[u]=fa;
depth[u]=depth[fa]+1;
int big=-2333;
size[u]=1;
for(int i=head[u];i;i=next[i]){
int v=to[i];
if(v==fa)continue;
dfs1(v,u);
size[u]+=size[v];
if(size[v]>big){
son[u]=v;
big=size[v];
}
}
}
int ccnt;
void dfs2(int u,int t){
ccnt++;
top[u]=t;
tid[u]=ccnt;
rnk[ccnt]=u;
if(son[u])dfs2(son[u],t);
for(int i=head[u];i;i=next[i]){
int v=to[i];
if(v==father[u])continue;
if(v==son[u])continue;
dfs2(v,v);
}
}
inline ll ls(ll x){
return x<<1;
}
inline ll rs(ll x){
return x<<1|1;
}
inline void push_up(ll x){
ans[x]=ans[ls(x)]+ans[rs(x)];
}
void build(ll x,ll l,ll r){
if(l==r){
ans[x]=a[l];
return;
}
ll mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
push_up(x);
}
inline void f(ll x,ll l,ll r,ll k){
tag[x]+=k;
ans[x]+=(r-l+1)*k;
}
inline void push_down(ll x,ll l,ll r){
ll mid=(l+r)>>1;
f(ls(x),l,mid,tag[x]);
f(rs(x),mid+1,r,tag[x]);
tag[x]=0;
}
ll query(ll ask_l,ll ask_r,ll l,ll r,ll x){
ll res=0;
if(ask_l<=l&&r<=ask_r){
return ans[x];
}
ll mid=(l+r)>>1;
push_down(x,l,r);
if(ask_l<=mid)res+=query(ask_l,ask_r,l,mid,ls(x));
if(ask_r>mid)res+=query(ask_l,ask_r,mid+1,r,rs(x));
return res;
}
void update(ll now_l,ll now_r,ll l,ll r,ll x,ll k){
if(now_l<=l&&r<=now_r){
f(x,l,r,k);
return;
}
ll mid=(l+r)>>1;
push_down(x,l,r);
if(now_l<=mid)update(now_l,now_r,l,mid,ls(x),k);
if(now_l>mid)update(now_l,now_r,mid+1,r,rs(x),k);
push_up(x);
}
inline int getn(int x,int y){
ll ans=0;
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]])swap(x,y);
ans+=query(tid[top[x]],tid[x],1,n,1)%p;
ans%=p;
x=father[top[x]];
}
if(depth[x]<depth[y]){
swap(x,y);
}
ans+=query(tid[y],tid[x],1,n,1)%p;
return ans%p;
}
inline void put(int x,int y,ll z){
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]])swap(x,y);
update(tid[top[x]],tid[x],1,n,1,z);
x=father[top[x]];
}
if(depth[x]<depth[y]){
swap(x,y);
}
update(tid[y],tid[x],1,n,1,z);
}
int main(){
scanf("%d%d%d%d",&n,&m,&r,&p);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs1(r,0);
dfs2(r,r);
build(1,1,n);
for(int i=1;i<=m;i++){
int k;
scanf("%d",&k);
if(k==1){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
put(x,y,z);
}
if(k==2){
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",getn(x,y));
}
if(k==3){
int x,z;
scanf("%d%d",&x,&z);
update(tid[x],tid[x]+size[x]-1,1,n,1,z);
}
if(k==4){
int x;
scanf("%d",&x);
printf("%lld\n",query(tid[x],tid[x]+size[x]-1,1,n,1));
}
}
return 0;
}
```
输入：
```
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
```
应该输出：
```
2
21
```
实际输出：
```
2
18
```
by Fractures @ 2019-08-03 08:45:07
@[Fractures](/space/show?uid=78791) emm，看看ZYF_B dalao说的吧qwq
by Ynoi @ 2019-08-03 08:46:07
@[ZYF_B](/space/show?uid=71514) 我没看见呢……谢谢大佬
by Fractures @ 2019-08-03 08:46:10
@[树链剖分](/space/show?uid=124721) qaq
by Fractures @ 2019-08-03 08:46:30
你把build中a[l]换成a[rnk[l]]就对了
by ZYF_B @ 2019-08-03 08:47:40
线段树中的值都是重新编号过后的，刚学确实容易弄混
by ZYF_B @ 2019-08-03 08:50:22