the_Dream_Chaser @ 2024-06-28 19:09:08
大佬玄关求调，90tps，只WA了最后一个点 代码如下
#include<bits/stdc++.h>
#define long long ll
const int MAXN=6e5+16;
using namespace std;
struct E{
int u,v,nxt;
}e[MAXN];
struct tree{
int l,r,w,siz,la;
}tr[MAXN];
int n,m,rot,Mod,cnt=0,a[MAXN],b[MAXN];
int head[MAXN];
int num=1;
void add(int x,int y){
e[++num].u=x;
e[num].v=y;
e[num].nxt=head[x];
head[x]=num;
}
int read(){
char c=getchar();int x=0,la=1;
while(c<'0'||c>'9'){if(c=='-')la=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();}
return x*la;
}
int dep[MAXN];//深度
int fa[MAXN];//父节点
int son[MAXN];//重儿子
int siz[MAXN];//子树的大小
int top[MAXN];//属于的重链的深度最浅的点编号
int dfn[MAXN];//点u的dfs序
int dfs1(int now,int la,int dp){//dfs1处理掉 dep,fa,son,siz数组
dep[now]=dp;
fa[now]=la;
siz[now]=1;
int maxson=-1;
for(int i=head[now];i!=-1;i=e[i].nxt){
if(e[i].v==la) continue;
siz[now]+=dfs1(e[i].v,now,dp+1);
if(siz[e[i].v]>maxson) maxson=siz[e[i].v],son[now]=e[i].v;
}
return siz[now];
//=siz[e[i].v];
}
void biu(int k,int ll,int rr){//建树
tr[k].l=ll;
tr[k].r=rr;
tr[k].siz=rr-ll+1;
if(ll==rr){
tr[k].w=a[ll];
return ;
}
int mid=(ll+rr)>>1;
biu(k<<1,ll,mid);
biu(k<<1|1,mid+1,rr);
tr[k].w=(tr[k<<1].w+tr[k<<1|1].w)%Mod;
}
void dfs2(int now,int tp){//dfs1处理掉 dfn,top数组
dfn[now]=++cnt;
a[cnt]=b[now];
top[now]=tp;
if(!son[now])return ;
dfs2(son[now],tp);
for(int i=head[now];i!=-1;i=e[i].nxt){
if(!dfn[e[i].v]){
dfs2(e[i].v,e[i].v);
}
}
}
void pushdown(int k){//传标记
if(!tr[k].la) return ;
tr[k<<1].w=(tr[k<<1].w+tr[k<<1].siz*tr[k].la)%Mod;
tr[k<<1|1].w=(tr[k<<1|1].w+tr[k<<1|1].siz*tr[k].la)%Mod;
tr[k<<1].la=(tr[k<<1].la+tr[k].la)%Mod;
tr[k<<1|1].la=(tr[k<<1|1].la+tr[k].la)%Mod;
tr[k].la=0;
}
void change(int k,int ll,int rr,int val){//区间修改
if(ll<=tr[k].l&&tr[k].r<=rr){
tr[k].w+=tr[k].siz*val;
tr[k].la+=val;
return ;
}
pushdown(k);
int mid=(tr[k].l+tr[k].r)>>1;
if(ll<=mid)change(k<<1,ll,rr,val);
if(rr>mid)change(k<<1|1,ll,rr,val);
tr[k].w=(tr[k<<1].w+tr[k<<1|1].w)%Mod;
}
int ask(int k,int ll,int rr){//区间求和
int ans=0;
if(ll<=tr[k].l&&tr[k].r<=rr)
return tr[k].w;
pushdown(k);
int mid=(tr[k].l+tr[k].r)>>1;
if(ll<=mid) ans=(ans+ask(k<<1,ll,rr))%Mod;
if(rr>mid) ans=(ans+ask(k<<1|1,ll,rr))%Mod;
return ans;
}
void sum(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,dfn[top[x]],dfn[x]))%Mod;
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ans=(ans+ask(1,dfn[x],dfn[y]))%Mod;
printf("%d\n",ans);
}
void Add(int x,int y,int val){//路径加值
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
change(1,dfn[top[x]],dfn[x],val);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
change(1,dfn[x],dfn[y],val);
}
int main(){
memset(head,-1,sizeof(head));
n=read();m=read();rot=read();Mod=read();
for(int w,i=1;i<=n;i++)b[i]=read();
for(int u,v,i=1;i<=n-1;i++){
u=read(),v=read();
add(u,v);
add(v,u);
}
dfs1(rot,0,1);
dfs2(rot,rot);
biu(1,1,n);
for(int i=1,op,x,y,z;i<=m;i++){
cin>>op;
if(op==1){
cin>>x>>y>>z;
z=z%Mod;
Add(x,y,z);
}
if(op==2){
cin>>x>>y;
sum(x,y);
}
if(op==3){
cin>>x>>z;
change(1,dfn[x],dfn[x]+siz[x]-1,z%Mod);
}
if(op==4){
cin>>x;
int ans=ask(1,dfn[x],dfn[x]+siz[x]-1);
cout<<ans<<endl;
}
}
}
/*
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
*/by JOKER_MAN @ 2024-06-28 19:13:03
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#define Rint register int
#define mem(a,b) memset(a,(b),sizeof(a))
#define Temp template<typename T>
using namespace std;
typedef long long LL;
Temp inline void read(T &x){
x=0;T w=1,ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
x=x*w;
}
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define len (r-l+1)
const int maxn=200000+10;
int n,m,r,mod;
//见题意
int e,beg[maxn],nex[maxn],to[maxn],w[maxn],wt[maxn];
//链式前向星数组，w[]、wt[]初始点权数组
int a[maxn<<2],laz[maxn<<2];
//线段树数组、lazy操作
int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn];
//son[]重儿子编号,id[]新编号,fa[]父亲节点,cnt dfs_clock/dfs序,dep[]深度,siz[]子树大小,top[]当前链顶端节点
int res=0;
//查询答案
inline void add(int x,int y){//链式前向星加边
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
}
//-------------------------------------- 以下为线段树
inline void pushdown(int rt,int lenn){
laz[rt<<1]+=laz[rt];
laz[rt<<1|1]+=laz[rt];
a[rt<<1]+=laz[rt]*(lenn-(lenn>>1));
a[rt<<1|1]+=laz[rt]*(lenn>>1);
a[rt<<1]%=mod;
a[rt<<1|1]%=mod;
laz[rt]=0;
}
inline void build(int rt,int l,int r){
if(l==r){
a[rt]=wt[l];
if(a[rt]>mod)a[rt]%=mod;
return;
}
build(lson);
build(rson);
a[rt]=(a[rt<<1]+a[rt<<1|1])%mod;
}
inline void query(int rt,int l,int r,int L,int R){
if(L<=l&&r<=R){res+=a[rt];res%=mod;return;}
else{
if(laz[rt])pushdown(rt,len);
if(L<=mid)query(lson,L,R);
if(R>mid)query(rson,L,R);
}
}
inline void update(int rt,int l,int r,int L,int R,int k){
if(L<=l&&r<=R){
laz[rt]+=k;
a[rt]+=k*len;
}
else{
if(laz[rt])pushdown(rt,len);
if(L<=mid)update(lson,L,R,k);
if(R>mid)update(rson,L,R,k);
a[rt]=(a[rt<<1]+a[rt<<1|1])%mod;
}
}
//---------------------------------以上为线段树
inline int qRange(int x,int y){
int ans=0;
while(top[x]!=top[y]){//当两个点不在同一条链上
if(dep[top[x]]<dep[top[y]])swap(x,y);//把x点改为所在链顶端的深度更深的那个点
res=0;
query(1,1,n,id[top[x]],id[x]);//ans加上x点到x所在链顶端 这一段区间的点权和
ans+=res;
ans%=mod;//按题意取模
x=fa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点
}
//直到两个点处于一条链上
if(dep[x]>dep[y])swap(x,y);//把x点深度更深的那个点
res=0;
query(1,1,n,id[x],id[y]);//这时再加上此时两个点的区间和即可
ans+=res;
return ans%mod;
}
inline void updRange(int x,int y,int k){//同上
k%=mod;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,1,n,id[top[x]],id[x],k);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
update(1,1,n,id[x],id[y],k);
}
inline int qSon(int x){
res=0;
query(1,1,n,id[x],id[x]+siz[x]-1);//子树区间右端点为id[x]+siz[x]-1
return res;
}
inline void updSon(int x,int k){//同上
update(1,1,n,id[x],id[x]+siz[x]-1,k);
}
inline void dfs1(int x,int f,int deep){//x当前节点，f父亲，deep深度
dep[x]=deep;//标记每个点的深度
fa[x]=f;//标记每个点的父亲
siz[x]=1;//标记每个非叶子节点的子树大小
int maxson=-1;//记录重儿子的儿子数
for(Rint i=beg[x];i;i=nex[i]){
int y=to[i];
if(y==f)continue;//若为父亲则continue
dfs1(y,x,deep+1);//dfs其儿子
siz[x]+=siz[y];//把它的儿子数加到它身上
if(siz[y]>maxson)son[x]=y,maxson=siz[y];//标记每个非叶子节点的重儿子编号
}
}
inline void dfs2(int x,int topf){//x当前节点，topf当前链的最顶端的节点
id[x]=++cnt;//标记每个点的新编号
wt[cnt]=w[x];//把每个点的初始值赋到新编号上来
top[x]=topf;//这个点所在链的顶端
if(!son[x])return;//如果没有儿子则返回
dfs2(son[x],topf);//按先处理重儿子，再处理轻儿子的顺序递归处理
for(Rint i=beg[x];i;i=nex[i]){
int y=to[i];
if(y==fa[x]||y==son[x])continue;
dfs2(y,y);//对于每一个轻儿子都有一条从它自己开始的链
}
}
int main(){
read(n);read(m);read(r);read(mod);
for(Rint i=1;i<=n;i++)read(w[i]);
for(Rint i=1;i<n;i++){
int a,b;
read(a);read(b);
add(a,b);add(b,a);
}
dfs1(r,0,1);
dfs2(r,r);
build(1,1,n);
while(m--){
int k,x,y,z;
read(k);
if(k==1){
read(x);read(y);read(z);
updRange(x,y,z);
}
else if(k==2){
read(x);read(y);
printf("%d\n",qRange(x,y));
}
else if(k==3){
read(x);read(y);
updSon(x,y);
}
else{
read(x);
printf("%d\n",qSon(x));
}
}
}by the_Dream_Chaser @ 2024-06-28 19:19:23
@johnhuang 所以我是哪里出问题导致最后一个点没过？
by sQrtN @ 2024-07-27 23:44:33
@the_Dream_Chaser 在输出的时候再模一下