@[signed](/user/241817)
`if(dep[top[u]]>dep[top[v]]){`是`<`
by ningago @ 2022-07-21 13:50:23
@[signed](/user/241817) build 函数中 `t[p].sum=pr[dfn[l]];` 这句有问题,dfn 数组是将树节点编号映射为 dfs 序编号,而这里应该将 dfs 序编号 l 映射为一个树节点编号来作为 pr 数组的下标
没细看,不清楚还有没有别的问题
by StarLbright40 @ 2022-07-21 13:53:52
@[ningago](/user/371968) 不是先跳深度大的嘛awa
by Chancylaser @ 2022-07-21 13:54:23
(刚才打了一堆字按发送结果帖子删了/fn
by StarLbright40 @ 2022-07-21 13:54:58
@[StarLbright40](/user/128570) 我试一下awa,谢谢
by Chancylaser @ 2022-07-21 13:55:35
@[signed](/user/241817) 我瞎了qwq
by ningago @ 2022-07-21 13:55:41
@[StarLbright40](/user/128570) 对不起,刚才发的不是最新代码awa
by Chancylaser @ 2022-07-21 13:56:08
还有 pushdown 里面可能会爆 int
by StarLbright40 @ 2022-07-21 13:56:48
@[StarLbright40](/user/128570) 如果您还有时间,能帮蒟蒻看看咩awa,感谢。
小改了一下,增加了一个数组a。
刚才您说的问题在build也改了,就是样例输出2错了。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,r,P;
int fst[N],nxt[N],tot,to[N];
int dep[N],f[N]; //记录每个点深度,父节点
int siz[N],son[N]; //记录:每个点子树大小 || 重儿子
void add_edge(int u,int v){
nxt[++tot]=fst[u];
fst[u]=tot;
to[tot]=v;
}
struct tree{
int l,r;
int sum,lazy;
}t[8*N];
void dfs1(int p){ //处理每个点子树大小 和 重儿子
siz[p]=1;
for(int i=fst[p];i;i=nxt[i]){
int s=to[i];
if(!dep[s]){
dep[s]=dep[p]+1;
f[s]=p;
dfs1(s);
siz[p]+=siz[s];
if(!son[p]||siz[s]>siz[son[p]])
son[p]=s;
}
}
}
int top[N],dfn[N],cnt;
//top是这个点所在重链顶点编号 ,dfn是记录p节点dfn序,
int a[N],pr[N]; // pr是输入时的点权 a将dfn序映射为树的点编号
void dfs2(int p,int t){
top[p]=t;
dfn[p]=++cnt;
a[cnt]=p;
if(!son[p]) return;
dfs2(son[p],t);
for(int i=fst[p];i;i=nxt[i])
if(to[i]!=son[p]&&to[i]!=f[p])
dfs2(to[i],to[i]);
}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
t[p].lazy=0;
if(l==r){
t[p].sum=pr[a[dfn[l]]];
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void pushdown(int p){
t[p<<1].lazy+=t[p].lazy , t[p<<1|1].lazy+=t[p].lazy;
t[p<<1].sum+=t[p].lazy*(t[p<<1].r-t[p<<1].l+1); t[p<<1].sum%=P;
t[p<<1|1].sum+=t[p].lazy*(t[p<<1|1].r-t[p<<1|1].l+1); t[p<<1|1].sum%=P;
t[p].lazy=0;
}
void add_sum(int p,int x,int y,int k){
if(t[p].l>y||t[p].r<x) return;
if(x<=t[p].l&&t[p].r<=y){
t[p].sum+=k*(t[p].r-t[p].l+1); t[p].sum%=P;
t[p].lazy+=k;
return;
}
if(t[p].lazy) pushdown(p);
add_sum(p<<1,x,y,k);
add_sum(p<<1|1,x,y,k);
t[p].sum=t[p<<1].sum+t[p<<1|1].sum; t[p].sum%=P;
}
int pr_sum(int p,int x,int y){
if(t[p].l>y||t[p].r<x) return 0;
if(t[p].l>=x&&t[p].r<=y) return t[p].sum;
if(t[p].lazy) pushdown(p);
int ans=0;
ans+=pr_sum(p<<1,x,y); ans%=P;
ans+=pr_sum(p<<1|1,x,y); ans%=P;
return ans;
}
void lca1(int u,int v,int k){
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]){
add_sum(1,dfn[top[u]],dfn[u],k);
u=f[top[u]];
}
else{
add_sum(1,dfn[top[v]],dfn[v],k);
v=f[top[v]];
}
}
if(dep[u]>dep[v]) swap(u,v);
add_sum(1,dfn[u],dfn[v],k);
}
int lca2(int u,int v){
int ans=0;
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]){
ans+=pr_sum(1,dfn[top[u]],dfn[u]); ans%=P;
u=f[top[u]];
}
else{
ans+=pr_sum(1,dfn[top[v]],dfn[v]); ans%=P;
v=f[top[v]];
}
}
if(dep[u]>dep[v]) swap(u,v);
ans+=pr_sum(1,dfn[u],dfn[v]); ans%=P;
return ans;
}
int main(){
cin>>n>>m>>r>>P; dep[r]=1;
for(int i=1;i<=n;i++) cin>>pr[i];
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
add_edge(x,y);
add_edge(y,x);
}
dfs1(r);
dfs2(r,r);
build(1,1,n);
for(int i=1;i<=m;i++){
int eps,x,y,z;
cin>>eps;
if(eps==1){
cin>>x>>y>>z;
lca1(x,y,z);
}
if(eps==2){
cin>>x>>y;
cout<<lca2(x,y)<<endl;
}
if(eps==3){
cin>>x>>z;
//cout<<a[x]<<" "<<a[x]+siz[x]-1<<endl;
add_sum(1,dfn[x],dfn[x]+siz[x]-1,z);
}
if(eps==4){
cin>>x;
cout<<pr_sum(1,dfn[x],dfn[x]+siz[x]-1)<<endl;
}
}
return 0;
}
```
by Chancylaser @ 2022-07-21 14:00:21
@[signed](/user/241817) 你改了个什么玩意/fn
仔细想想你开的数组的作用,`a[dfn[l]]` 它不就是 `l` 吗(
by StarLbright40 @ 2022-07-21 14:03:57