3 条题解
-
0
看见没有有注释的代码，水一篇(记得用c++看)
话说这一百多行的代码真的能背吗?#include<bits/stdc++.h> #define lc(x) tr[x].ch[0] #define rc(x) tr[x].ch[1] #define fa(x) tr[x].fa #define notroot(x) lc(fa(x))==x||rc(fa(x))==x using namespace std; const int N=3e5+10; struct node{int ch[2],fa,s,v,tag,tag1;}tr[N];//tag1给子树的懒标记,s表示最大值 pair<int,int>e[N];//别忘了 void pu(int p){tr[p].s=max({lc(p)?tr[lc(p)].s:0,tr[p].v,rc(p)?tr[rc(p)].s:0});} void pd(int p) { if(tr[p].tag1)//往下传递 { tr[lc(p)].v+=tr[p].tag1; tr[rc(p)].v+=tr[p].tag1; tr[lc(p)].s+=tr[p].tag1; tr[rc(p)].s+=tr[p].tag1; tr[rc(p)].tag1+=tr[p].tag1; tr[lc(p)].tag1+=tr[p].tag1; tr[p].tag1=0; } if(tr[p].tag) { swap(lc(p),rc(p)); tr[lc(p)].tag^=1; tr[rc(p)].tag^=1; tr[p].tag=0; } } void pa(int x){if(notroot(x))pa(fa(x));pd(x);} void rotate(int x) { int y=fa(x),z=fa(y),k=rc(y)==x; if(notroot(y))tr[z].ch[rc(z)==y]=x;fa(x)=z; tr[y].ch[k]=tr[x].ch[k^1];fa(tr[y].ch[k])=y;//这里不一样!!! tr[x].ch[k^1]=y;fa(y)=x; pu(y),pu(x); } void splay(int x) { pa(x); while(notroot(x)) { int y=fa(x),z=fa(y); if(notroot(y))(rc(y)==x)^(lc(z)==y)?rotate(x):rotate(y); rotate(x); } } void access(int x) { for(int y=0;x;) { splay(x); rc(x)=y; pu(x); y=x;x=fa(x); } } void makeroot(int x) { access(x); splay(x); tr[x].tag^=1; } void split(int x,int y) { makeroot(x); access(y); splay(y); } int findroot(int x) { access(x); splay(x); while(lc(x))pd(x),x=lc(x); splay(x); return x; } void output(int x,int y) { if(findroot(y)!=findroot(x)){puts("-1");return ;}//判断是否是违法操作 split(x,y); printf("%d\n",tr[y].s); } void link(int x,int y) { makeroot(x); if(findroot(y)!=x)fa(x)=y; } bool cut(int x,int y)//进行拆边,顺便返回是不是违法操作 { makeroot(x); if(findroot(y)==x&&fa(y)==x&&!lc(y)) { fa(y)=0;pu(x); return 1; } return 0; } int main() { int n,q;scanf("%d",&n); for(int i=1;i<n;i++)scanf("%d%d",&e[i].first,&e[i].second);//先用数组存着,后面在建图 for(int i=1;i<=n;i++)scanf("%d",&tr[i].v),tr[i].s=tr[i].v; for(int i=1;i<n;i++)link(e[i].first,e[i].second); scanf("%d",&q); while(q--) { int op,k,x,y;scanf("%d",&op); if(op==1) { scanf("%d%d",&x,&y); if(x==y||findroot(x)==findroot(y))puts("-1");//违法操作 else link(x,y); } else if(op==2) { scanf("%d%d",&x,&y); if(x==y||!cut(x,y))puts("-1"); } else if(op==3) { scanf("%d%d%d",&k,&x,&y); if(findroot(x)!=findroot(y)){puts("-1");continue;}//违法操作 split(x,y); tr[y].s+=k;//别忘了给自己加 tr[y].v+=k; tr[y].tag1+=k; } else { scanf("%d%d",&x,&y); output(x,y);//输出 } } return 0; } -
0
#include<bits/stdc++.h> using namespace std; const int N=3e5+10; #define lc(p) tr[p].ch[0] #define rc(p) tr[p].ch[1] #define fa(p) tr[p].f struct node{int ch[2],f,s,v,tag,tag1;}tr[N];pair<int,int>e[N]; bool notrt(int p){return lc(fa(p))==p||rc(fa(p))==p;} void pushup(int p){tr[p].s=max({lc(p)?tr[lc(p)].s:0,tr[p].v,rc(p)?tr[rc(p)].s:0});} void pushdown(int p) { if(tr[p].tag1) { tr[lc(p)].v+=tr[p].tag1; tr[rc(p)].v+=tr[p].tag1; tr[lc(p)].s+=tr[p].tag1; tr[rc(p)].s+=tr[p].tag1; tr[lc(p)].tag1+=tr[p].tag1; tr[rc(p)].tag1+=tr[p].tag1; tr[p].tag1=0; } if(tr[p].tag) { swap(lc(p),rc(p)); tr[lc(p)].tag^=1,tr[rc(p)].tag^=1; tr[p].tag=0; } } void pushall(int p) { if(notrt(p))pushall(fa(p)); pushdown(p); } void rotate(int x) { int y=fa(x),z=fa(y),k=rc(y)==x; if(notrt(y))tr[z].ch[rc(z)==y]=x;fa(x)=z; tr[y].ch[k]=tr[x].ch[k^1];fa(tr[y].ch[k])=y; tr[x].ch[k^1]=y;fa(y)=x; pushup(y);pushup(x); } void splay(int x) { pushall(x); while(notrt(x)) { int y=fa(x),z=fa(y); if(notrt(y))((rc(y)==x)^(rc(z)==y))?rotate(x):rotate(y); rotate(x); } } void access(int x) { for(int y=0;x;) { splay(x); rc(x)=y; pushup(x); y=x;x=fa(x); } } void makert(int x) { access(x); splay(x); tr[x].tag^=1; } void split(int x,int y) { makert(x); access(y); splay(y); } int findrt(int x) { access(x); splay(x); while(lc(x))pushdown(x),x=lc(x); splay(x); return x; } void output(int x,int y) { if(findrt(y)!=findrt(x)){cout<<-1<<'\n';return;} split(x,y); cout<<tr[y].s<<'\n'; } void link(int x,int y) { makert(x); if(findrt(y)!=x) fa(x)=y; } bool cut(int x,int y) { makert(x); if(findrt(y)==x&&fa(y)==x&&!lc(y)) { fa(y)=0,pushup(x); return 1; } return 0; } int main() { int n,q;cin>>n; for(int i=1;i<n;i++)cin>>e[i].first>>e[i].second; for(int i=1;i<=n;i++)cin>>tr[i].v,tr[i].s=tr[i].v; for(int i=1;i<n;i++)link(e[i].first,e[i].second); cin>>q; while(q--) { int op,k,x,y;cin>>op; if(op==1) { cin>>x>>y; if(x==y||findrt(x)==findrt(y))cout<<-1<<'\n'; else link(x,y); } if(op==2) { cin>>x>>y; if(x==y||!cut(x,y))cout<<-1<<'\n'; } if(op==3) { cin>>k>>x>>y; if(findrt(x)!=findrt(y)){cout<<-1<<'\n';continue;} split(x,y); tr[y].s+=k; tr[y].v+=k; tr[y].tag1+=k; } if(op==4) { cin>>x>>y; output(x,y); } } return 0; } -
0
#include<cstdio> using namespace std; int max(int x,int y){return x>y?x:y;} void swap(int &x,int &y){int t=x;x=y;y=t;} struct node { int f,son[2],d,lazy,c,maxx; bool fz; node(){fz=false;} }tr[300005]; void lz(int x) { tr[x].d+=tr[x].lazy;tr[x].maxx+=tr[x].lazy; int lc=tr[x].son[0],rc=tr[x].son[1]; if(lc!=0)tr[lc].lazy+=tr[x].lazy; if(rc!=0)tr[rc].lazy+=tr[x].lazy; tr[x].lazy=0; } void whfz(int x) { int lc=tr[x].son[0],rc=tr[x].son[1]; if(lc!=0)tr[lc].fz=!tr[lc].fz; if(rc!=0)tr[rc].fz=!tr[rc].fz; swap(tr[x].son[0],tr[x].son[1]); tr[x].fz=false; } void update(int x) { int lc=tr[x].son[0],rc=tr[x].son[1]; if(tr[lc].lazy)lz(lc); if(tr[rc].lazy)lz(rc); tr[x].c=tr[lc].c+tr[rc].c+1; tr[x].maxx=max(tr[lc].maxx,tr[rc].maxx); tr[x].maxx=max(tr[x].maxx,tr[x].d); } void rotate(int x,int w) { int f=tr[x].f,ff=tr[tr[x].f].f; tr[f].son[1-w]=tr[x].son[w]; if(tr[x].son[w]!=0)tr[tr[x].son[w]].f=f; update(f); tr[x].son[w]=f;tr[f].f=x; update(x); if(tr[ff].son[0]==f)tr[ff].son[0]=x; else if(tr[ff].son[1]==f)tr[ff].son[1]=x; tr[x].f=ff; } void dfs(int x,int rt) { if(tr[x].f!=rt&&(tr[tr[x].f].son[0]==x||tr[tr[x].f].son[1]==x))dfs(tr[x].f,rt); if(tr[x].fz)whfz(x); if(tr[x].lazy!=0)lz(x); } void splay(int x,int rt) { dfs(x,rt); while(tr[x].f!=rt&&(tr[tr[x].f].son[0]==x||tr[tr[x].f].son[1]==x)) { int f=tr[x].f,ff=tr[tr[x].f].f; if(ff==rt||(tr[ff].son[0]!=f&&tr[ff].son[1]!=f)) { if(tr[f].son[0]==x)rotate(x,1); else rotate(x,0); } else { if(tr[f].son[0]==x&&tr[ff].son[0]==f){rotate(f,1);rotate(x,1);} else if(tr[f].son[1]==x&&tr[ff].son[1]==f){rotate(f,0);rotate(x,0);} else if(tr[f].son[0]==x&&tr[ff].son[1]==f){rotate(x,1);rotate(x,0);} else if(tr[f].son[1]==x&&tr[ff].son[0]==f){rotate(x,0);rotate(x,1);} } } } void access(int x) { int y=0; while(x!=0) { splay(x,0); tr[x].son[1]=y; if(y!=0)tr[y].f=x; y=x;x=tr[x].f; } } void makeroot(int x) { access(x);splay(x,0);tr[x].fz=!tr[x].fz; } int findroot(int x) { access(x);splay(x,0); while(tr[x].son[0]!=0)x=tr[x].son[0]; return x; } void link(int x,int y) { makeroot(x);tr[x].f=y;access(x); } bool cut(int x,int y) { makeroot(x);access(y);splay(y,0); if(findroot(y)!=x||tr[x].f!=y||tr[x].son[1]!=0)return false; tr[tr[y].son[0]].f=0;tr[y].son[0]=0; update(y); return true; } int xx[300005],yy[300005]; int main() { int n,m;scanf("%d",&n); for(int i=1;i<n;i++)scanf("%d%d",&xx[i],&yy[i]); for(int i=1;i<=n;i++) { scanf("%d",&tr[i].d); tr[i].maxx=tr[i].d; tr[i].c=1; } for(int i=1;i<n;i++)link(xx[i],yy[i]); scanf("%d",&m); while(m--) { int cz;scanf("%d",&cz); if(cz==1) { int x,y;scanf("%d%d",&x,&y); if(x==y||findroot(x)==findroot(y))puts("-1"); else link(x,y); } else if(cz==2) { int x,y;scanf("%d%d",&x,&y); if(x==y||!cut(x,y))puts("-1"); } else if(cz==3) { int w,x,y;scanf("%d%d%d",&w,&x,&y); if(findroot(x)!=findroot(y))puts("-1"); else { makeroot(x);access(y);splay(y,0); tr[y].lazy+=w; } } else if(cz==4) { int x,y;scanf("%d%d",&x,&y); if(findroot(x)!=findroot(y))puts("-1"); else { makeroot(x);access(y);splay(y,0);update(y); printf("%d\n",tr[y].maxx); } } } return 0; }
yanchengyi2024
LV 9
@ 2026-1-15 13:06:17
- 1