zengziqvan @ 2024-05-18 11:31:42
样例没过
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
//#define int long long
//#define double long double
#define FOR(i,l,r) for(int i=l;i<=r;++i)
#define ROF(i,r,l) for(int i=r;i>=l;--i)
#define mkp make_pair
#define fr first
#define se second
#define pb emplace_back
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
const int N=1e5+10;
int n,m,rt,Mo,a[N],b[N],cnt,siz[N],son[N],fa[N],dep[N],idx[N],top[N];
vector<int>e[N];
void dfs1(int x,int fat) {
fa[x]=fat;
siz[x]=1;
dep[x]=dep[fat]+1;
for(int y:e[x]) {
if(y==fat) continue;
dfs1(y,x);
siz[x]+=siz[y];
if(siz[son[x]]<siz[y]) son[x]=y;
}
}
void dfs2(int x,int tp) {
idx[x]=++cnt;
top[x]=tp;
if(!son[x]) return ;
dfs2(son[x],tp);
for(int y:e[x]) {
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
struct SegmentTree {
int l,r,sum,tag,en;
} t[N<<2];
void push_up(int p) {
t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%Mo;
}
void Build(int p,int l,int r) {
t[p].l=l,t[p].r=r,t[p].en=r-l+1;
if(l==r) return (void)(t[p].sum=a[idx[l]]);
int mid=l+r>>1;
Build(p<<1,l,mid);
Build(p<<1|1,mid+1,r);
push_up(p);
}
void push_down(int p) {
if(!t[p].tag) return ;
t[p<<1].sum=(t[p<<1].sum+t[p<<1].en*t[p].tag%Mo)%Mo;
t[p<<1|1].sum=(t[p<<1|1].sum+t[p<<1|1].en*t[p].tag%Mo)%Mo;
t[p<<1].tag+=t[p].tag;
t[p<<1].tag%=Mo;
t[p<<1|1].tag+=t[p].tag;
t[p<<1|1].tag%=Mo;
t[p].tag=0;
}
void change(int p,int l,int r,int x) {
if(l<=t[p].l&&t[p].r<=r) return (void)(t[p].tag=(t[p].tag+x)%Mo,t[p].sum=(t[p].sum+t[p].en*x%Mo)%Mo);
push_down(p);
int mid=t[p].l+t[p].r>>1;
if(l<=mid) change(p<<1,l,r,x);
if(r>mid) change(p<<1|1,l,r,x);
push_up(p);
}
int ask(int p,int l,int r) {
if(l<=t[p].l&&t[p].r<=r) return t[p].sum;
int mid=t[p].l+t[p].r>>1,val;
push_down(p);
if(l<=mid) val=(val+ask(p<<1,l,r))%Mo;
if(r>mid) val=(val+ask(p<<1|1,l,r))%Mo;
return val;
}
int Treeask(int x,int y) {
int ans=0;
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans=(ans+ask(1,idx[top[x]],top[x]))%Mo;
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans=(ans+ask(1,idx[x],idx[y]))%Mo;
return ans;
}
void Treeupdate(int x,int y,int z) {
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]]) swap(x,y);
change(1,idx[top[x]],idx[x],z);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
change(1,idx[x],idx[y],z);
}
main() {
cin>>n>>m>>rt>>Mo;
FOR(i,1,n) scanf("%d",&a[i]);
FOR(i,1,n-1) {
int u,v;
scanf("%d%d",&u,&v);
e[u].pb(v);
e[v].pb(u);
}
dfs1(rt,0),dfs2(rt,rt);
Build(1,1,n);
while(m--) {
int op,x,y,z;
scanf("%d",&op);
if(op==1) {
scanf("%d%d%d",&x,&y,&z);
Treeupdate(x,y,z%Mo);
}
if(op==2) {
scanf("%d%d",&x,&y);
printf("%d\n",Treeask(x,y));
}
if(op==3) {
scanf("%d%d",&x,&z);
change(1,idx[x],idx[x]+siz[x]-1,z%Mo);
}
if(op==4) {
scanf("%d",&x);
printf("%d\n",ask(1,idx[x],idx[x]+siz[x]-1));
}
}
return 0;
}by Tim0509 @ 2024-05-18 11:45:10
if(l==r) return (void)(t[p].sum=a[idx[l]]);
build 锅了
t[p].sum 是 l 作为 dfs序所对应的节点 的值。
by Tim0509 @ 2024-05-18 11:45:24
@zengziqvan
by zengziqvan @ 2024-05-18 11:49:49
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
//#define int long long
//#define double long double
#define FOR(i,l,r) for(int i=l;i<=r;++i)
#define ROF(i,r,l) for(int i=r;i>=l;--i)
#define mkp make_pair
#define fr first
#define se second
#define pb emplace_back
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
const int N=1e5+10;
int n,m,rt,Mo,a[N],b[N],cnt,siz[N],son[N],fa[N],dep[N],idx[N],top[N];
vector<int>e[N];
void dfs1(int x,int fat) {
fa[x]=fat;
siz[x]=1;
dep[x]=dep[fat]+1;
for(int y:e[x]) {
if(y==fat) continue;
dfs1(y,x);
siz[x]+=siz[y];
if(siz[son[x]]<siz[y]) son[x]=y;
}
}
void dfs2(int x,int tp) {
idx[x]=++cnt;
a[cnt]=b[x];
top[x]=tp;
if(!son[x]) return ;
dfs2(son[x],tp);
for(int y:e[x]) {
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
struct SegmentTree {
int l,r,sum,tag,en;
} t[N<<2];
void push_up(int p) {
t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%Mo;
}
void Build(int p,int l,int r) {
t[p].l=l,t[p].r=r,t[p].en=r-l+1;
if(l==r) return (void)(t[p].sum=a[l]);
int mid=l+r>>1;
Build(p<<1,l,mid);
Build(p<<1|1,mid+1,r);
push_up(p);
}
void push_down(int p) {
if(!t[p].tag) return ;
t[p<<1].sum=(t[p<<1].sum+t[p<<1].en*t[p].tag%Mo)%Mo;
t[p<<1|1].sum=(t[p<<1|1].sum+t[p<<1|1].en*t[p].tag%Mo)%Mo;
t[p<<1].tag+=t[p].tag;
t[p<<1].tag%=Mo;
t[p<<1|1].tag+=t[p].tag;
t[p<<1|1].tag%=Mo;
t[p].tag=0;
}
void change(int p,int l,int r,int x) {
if(l<=t[p].l&&t[p].r<=r) return (void)(t[p].tag=(t[p].tag+x)%Mo,t[p].sum=(t[p].sum+t[p].en*x%Mo)%Mo);
push_down(p);
int mid=t[p].l+t[p].r>>1;
if(l<=mid) change(p<<1,l,r,x);
if(r>mid) change(p<<1|1,l,r,x);
push_up(p);
}
int ask(int p,int l,int r) {
if(l<=t[p].l&&t[p].r<=r) return t[p].sum;
int mid=t[p].l+t[p].r>>1,val;
push_down(p);
if(l<=mid) val=(val+ask(p<<1,l,r))%Mo;
if(r>mid) val=(val+ask(p<<1|1,l,r))%Mo;
return val;
}
int Treeask(int x,int y) {
int ans=0;
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans=(ans+ask(1,idx[top[x]],top[x]))%Mo;
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans=(ans+ask(1,idx[x],idx[y]))%Mo;
return ans;
}
void Treeupdate(int x,int y,int z) {
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]]) swap(x,y);
change(1,idx[top[x]],idx[x],z);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
change(1,idx[x],idx[y],z);
}
main() {
cin>>n>>m>>rt>>Mo;
FOR(i,1,n) scanf("%d",&b[i]);
FOR(i,1,n-1) {
int u,v;
scanf("%d%d",&u,&v);
e[u].pb(v);
e[v].pb(u);
}
dfs1(rt,0),dfs2(rt,rt);
Build(1,1,n);
while(m--) {
int op,x,y,z;
scanf("%d",&op);
if(op==1) {
scanf("%d%d%d",&x,&y,&z);
Treeupdate(x,y,z%Mo);
}
if(op==2) {
scanf("%d%d",&x,&y);
printf("%d\n",Treeask(x,y));
}
if(op==3) {
scanf("%d%d",&x,&z);
change(1,idx[x],idx[x]+siz[x]-1,z%Mo);
}
if(op==4) {
scanf("%d",&x);
printf("%d\n",ask(1,idx[x],idx[x]+siz[x]-1));
}
}
return 0;
}by zengziqvan @ 2024-05-18 11:50:07
改了还是不过样例
by Tim0509 @ 2024-05-18 12:11:03
ask 里的 val 没初始化
以及 Treeask里ans=(ans+ask(1,idx[top[x]],top[x]))%Mo;改成ans=(ans+ask(1,idx[top[x]],idx[x]))%Mo;
by Tim0509 @ 2024-05-18 12:11:55
@zengziqvan
by zengziqvan @ 2024-05-18 13:20:53
@Tim0509 万分感谢，已关！