题目传送门
这 算是link-cut-tree裸题啊 不过以前好像没有写过单点修改..............
#include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std; const int M=50007; int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f; } int n,m,c[M][2],fa[M],a[M],b[M]; LL v[M],sum[M],mx[M]; bool rev[M]; bool isrt(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;} void up(int x){ if(!x) return ; mx[x]=v[x]; sum[x]=v[x]; int l=c[x][0],r=c[x][1]; if(l) mx[x]=max(mx[x],mx[l]),sum[x]+=sum[l]; if(r) mx[x]=max(mx[x],mx[r]),sum[x]+=sum[r]; } void down(int x){ if(!rev[x]) return ; rev[x]=0; int l=c[x][0],r=c[x][1]; if(l) swap(c[l][0],c[l][1]),rev[l]^=1; if(r) swap(c[r][0],c[r][1]),rev[r]^=1; } void rotate(int x){ int y=fa[x],z=fa[y],l=0,r=1; if(c[y][1]==x) l=1,r=0; if(!isrt(y)) c[z][c[z][1]==y]=x; fa[y]=x; fa[x]=z; fa[c[x][r]]=y; c[y][l]=c[x][r]; c[x][r]=y; up(y); up(x); } int st[M],top=0,S; void splay(int x){ st[++top]=x; for(int i=x;!isrt(i);i=fa[i]) st[++top]=fa[i]; while(top) down(st[top--]); while(!isrt(x)){ int y=fa[x],z=fa[y]; if(!isrt(y)){ if(c[z][0]==y^c[y][0]==x) rotate(x); else rotate(y); } rotate(x); } } void acs(int x0){ for(int x=x0,y=0;x;splay(x),c[x][1]=y,up(x),y=x,x=fa[x]); splay(x0); } void mrt(int x){acs(x); swap(c[x][0],c[x][1]); rev[x]^=1;} void link(int x,int y){mrt(x); fa[x]=y;} void spl(int x,int y){mrt(x); acs(y);} int main() { int x,y; n=read(); for(int i=1;i<n;i++) a[i]=read(),b[i]=read(); for(int i=1;i<=n;i++) v[i]=read(); for(int i=1;i<n;i++) link(a[i],b[i]); m=read(); char ch[15]; for(int i=1;i<=m;i++){ scanf("%s",ch); x=read(); y=read(); if(ch[1]=='H') acs(x),v[x]=y; if(ch[1]=='S') spl(x,y),printf("%lld\n",sum[y]); if(ch[1]=='M') spl(x,y),printf("%lld\n",mx[y]); } return 0; }
