Frielen @ 2024-06-20 13:36:42
评测记录
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define ls(x) x<<1
#define rs(x) x<<1|1
#define next Next
const int N=1e5+9;
int n,m,r,M;
struct Node{
int to,next;
}edge[N<<1];
int head[N<<1],cnt;
void in(){
for(int i=0;i<=n<<1;i++){
edge[i].next=-1;
head[i]=-1;
}
}
void add_Node(int u,int v){
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=++cnt;
}
int tree[N<<2],tag[N<<2],Point[N],N_Point[N];
void add_tag(int p,int pl,int pr,int d){
tag[p]+=d;
tree[p]+=d*(pr-pl+1);
tree[p]%=M;
}
void push_up(int p){
tree[p]=tree[ls(p)]+tree[rs(p)];
tree[p]%=M;
}
void push_down(int p,int pl,int pr){
if(tag[p]){
int mid=(pl+pr)>>1;
add_tag(ls(p),pl,mid,tag[p]);
add_tag(rs(p),mid+1,pr,tag[p]);
tag[p]=0;
}
}
void build_tree(int p,int pl,int pr){
tag[p]=0;
if(pl==pr){
tree[p]=N_Point[pl];
tree[p]%=M;
return;
}
int mid=(pl+pr)>>1;
build_tree(ls(p),pl,mid);
build_tree(rs(p),mid+1,pr);
push_up(p);
}
void update(int L,int R,int p,int pl,int pr,int d){
if(pl>=L&&pr<=R){
add_tag(p,pl,pr,d);
return;
}
push_down(p,pl,pr);
int mid=(pl+pr)>>1;
if(L<=mid) update(L,R,ls(p),pl,mid,d);
if(R>mid) update(L,R,rs(p),mid+1,pr,d);
push_up(p);
}
int query(int L,int R,int p,int pl,int pr){
if(pl>=L&&pr<=R) return tree[p]%M;
push_down(p,pl,pr);
int res=0,mid=(pl+pr)>>1;
if(L<=mid) res+=query(L,R,ls(p),pl,mid);
if(R>mid) res+=query(L,R,rs(p),mid+1,pr);
return res;
}
int dis[N],sz[N],son[N],top[N],dad[N],id[N],num;
void dfs1(int x,int fa){
dis[x]=dis[fa]+1;
dad[x]=fa;
for(int i=head[x];~i;i=edge[i].next){
int k=edge[i].to;
if(k!=fa){
dad[k]=x;
dfs1(k,x);
sz[x]+=sz[k];
if(!son[x]||sz[son[x]]<sz[k])
son[x]=k;
}
}
}
void dfs2(int x,int Top){
id[x]+=num;
N_Point[num]=Point[x];
top[x]+=Top;
if(!son[x]) return;
dfs2(son[x],Top);
for(int i=head[x];~i;i=edge[i].next){
int k=edge[i].to;
if(k!=dad[x]&&k!=son[x])
dfs2(k,k);
}
}
void Point_Z(int x,int y,int z){
while(top[x]!=top[y]){
if(dis[top[x]]<dis[top[y]])
swap(x,y);
update(id[top[x]],id[x],1,1,n,z);
x=dad[top[x]];
}
if(dis[x]>dis[y]) swap(x,y);
update(id[x],id[y],1,1,n,z);
}
int comp_Point(int x,int y){
int res=0;
while(top[x]!=top[y]){
if(dis[top[x]]<dis[top[y]]) swap(x,y);
res+=query(id[top[x]],id[x],1,1,n);
res%=M;
x=dad[top[x]];
}
if(dis[x]>dis[y]) swap(x,y);
res+=query(id[x],id[y],1,1,n);
return res;
}
int main(){
in();
scanf("%d%d%d%d",&n,&m,&r,&M);
for(int i=1;i<=n;i++)
scanf("%d",&Point[i]);
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
add_Node(u,v);
add_Node(v,u);
}
dfs1(r,0);
dfs2(r,r);
build_tree(1,1,n);
while(m--){
int k,x,y,z;
scanf("%d",&k);
if(k==1){
scanf("%d%d%d",&x,&y,&z);
Point_Z(x,y,z);
}
if(k==2){
scanf("%d%d",&x,&y);
printf("%d\n",comp_Point(x,y));
}
if(k==3){
scanf("%d%d",&x,&y);
update(id[x],id[x]+sz[x]-1,1,1,n,y);
}
if(k==4){
scanf("%d",&x);
printf("%d\n",query(id[x],id[x]+sz[x]-1,1,1,n)%M);
}
}
return 0;
}是根据《算法竞赛》的思路写的,dalao帮忙看看，谢谢！（我是蒟蒻）
by Q23linrunlin @ 2024-06-20 14:06:33
还不错！！ 虽然……
by _LSA_ @ 2024-06-20 14:25:17
把in()函数移到输入n之后 @Frielen
不过还是死循环，我再找一下
by _LSA_ @ 2024-06-20 14:27:39
dfs2函数第一行补上num++
by _LSA_ @ 2024-06-20 14:29:53
dfs1第一行加上sz[x]=1(不是你这代码怎么问题这么多
by _LSA_ @ 2024-06-20 14:34:31
add_Node中
head[u]=++cnt;
改成head[u]=cnt++;
by _LSA_ @ 2024-06-20 14:37:59
上面改完就能过样例了 @Frielen
by _LSA_ @ 2024-06-20 14:42:14
帮你交了一发WA 37分QwQ
by Frielen @ 2024-06-20 16:04:07
@LSA 感谢大佬！qwp
by _LSA_ @ 2024-06-20 16:07:11
@Frielen 你comp_Point最后忘取模了，取模完就过了。
by _LSA_ @ 2024-06-20 16:08:18
帮你改好的代码，改的地方后面有注释QwQ
#include<bits/stdc++.h>
using namespace std;
#define ls(x) x<<1
#define rs(x) x<<1|1
#define next Next
const int N=1e5+9;
int n,m,r,M;
struct Node{
int to,next;
}edge[N<<1];
int head[N<<1],cnt;
void in(){
for(int i=0;i<=n<<1;i++){
edge[i].next=-1;
head[i]=-1;
}
}
void add_Node(int u,int v){
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++; // 1
}
int tree[N<<2],tag[N<<2],Point[N],N_Point[N];
void add_tag(int p,int pl,int pr,int d){
tag[p]+=d;
tree[p]+=d*(pr-pl+1);
tree[p]%=M;
}
void push_up(int p){
tree[p]=tree[ls(p)]+tree[rs(p)];
tree[p]%=M;
}
void push_down(int p,int pl,int pr){
if(tag[p]){
int mid=(pl+pr)>>1;
add_tag(ls(p),pl,mid,tag[p]);
add_tag(rs(p),mid+1,pr,tag[p]);
tag[p]=0;
}
}
void build_tree(int p,int pl,int pr){
tag[p]=0;
if(pl==pr){
tree[p]=N_Point[pl];
tree[p]%=M;
return;
}
int mid=(pl+pr)>>1;
build_tree(ls(p),pl,mid);
build_tree(rs(p),mid+1,pr);
push_up(p);
}
void update(int L,int R,int p,int pl,int pr,int d){
if(pl>=L&&pr<=R){
add_tag(p,pl,pr,d);
return;
}
push_down(p,pl,pr);
int mid=(pl+pr)>>1;
if(L<=mid) update(L,R,ls(p),pl,mid,d);
if(R>mid) update(L,R,rs(p),mid+1,pr,d);
push_up(p);
}
int query(int L,int R,int p,int pl,int pr){
if(pl>=L&&pr<=R) return tree[p]%M;
push_down(p,pl,pr);
int res=0,mid=(pl+pr)>>1;
if(L<=mid) res+=query(L,R,ls(p),pl,mid);
if(R>mid) res+=query(L,R,rs(p),mid+1,pr);
return res;
}
int dis[N],sz[N],son[N],top[N],dad[N],id[N],num;
void dfs1(int x,int fa){
sz[x] = 1; // 2
dis[x]=dis[fa]+1;
dad[x]=fa;
for(int i=head[x];~i;i=edge[i].next){
int k=edge[i].to;
if(k!=fa){
dad[k]=x;
dfs1(k,x);
sz[x]+=sz[k];
if(!son[x]||sz[son[x]]<sz[k])
son[x]=k;
}
}
}
void dfs2(int x,int Top){
num++; // 3
id[x]+=num;
N_Point[num]=Point[x];
top[x]+=Top;
if(!son[x]) return;
dfs2(son[x],Top);
for(int i=head[x];~i;i=edge[i].next){
int k=edge[i].to;
if(k!=dad[x]&&k!=son[x])
dfs2(k,k);
}
}
void Point_Z(int x,int y,int z){
while(top[x]!=top[y]){
if(dis[top[x]]<dis[top[y]])
swap(x,y);
update(id[top[x]],id[x],1,1,n,z);
x=dad[top[x]];
}
if(dis[x]>dis[y]) swap(x,y);
update(id[x],id[y],1,1,n,z);
}
int comp_Point(int x,int y){
int res=0;
while(top[x]!=top[y]){
if(dis[top[x]]<dis[top[y]]) swap(x,y);
res+=query(id[top[x]],id[x],1,1,n);
res%=M;
x=dad[top[x]];
}
if(dis[x]>dis[y]) swap(x,y);
res+=query(id[x],id[y],1,1,n);
return res;
}
int main(){
scanf("%d%d%d%d",&n,&m,&r,&M);
in(); // 4
for(int i=1;i<=n;i++)
scanf("%d",&Point[i]);
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
add_Node(u,v);
add_Node(v,u);
}
dfs1(r,0);
dfs2(r,r);
build_tree(1,1,n);
while(m--){
int k,x,y,z;
scanf("%d",&k);
if(k==1){
scanf("%d%d%d",&x,&y,&z);
Point_Z(x,y,z);
}
if(k==2){
scanf("%d%d",&x,&y);
printf("%d\n",comp_Point(x,y)%M);//5
}
if(k==3){
scanf("%d%d",&x,&y);
update(id[x],id[x]+sz[x]-1,1,1,n,y);
}
if(k==4){
scanf("%d",&x);
printf("%d\n",query(id[x],id[x]+sz[x]-1,1,1,n)%M);
}
}
return 0;
}