题目：https://www.luogu.org/problemnew/show/P4546
先写了个55分的部分分，直接用LCT维护即可，在洛谷上拿了60分；
注意各处 pushup，而且 splay 维护的是一条链但其形态不一定是一条链！
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; int rd() { int ret=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return f?ret:-ret; } typedef double db; int const xn=1e5+5; int n,m,hd[xn],f[xn],fa[xn],c[xn][2],rev[xn]; db A[xn],B[xn],sum[xn]; char tp[10],op[15]; bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;} db cal(int x,db v){db y=A[x]*v+B[x]; if(f[x]==1)return sin(y); if(f[x]==2)return exp(y); return y;} void pushup(int x){sum[x]=cal(x,1)+sum[c[x][0]]+sum[c[x][1]];} void rotate(int x) { int y=fa[x],z=fa[y],d=(c[y][1]==x); if(!isroot(y))c[z][c[z][1]==y]=x; fa[x]=z; fa[y]=x; fa[c[x][!d]]=y; c[y][d]=c[x][!d]; c[x][!d]=y; pushup(y); pushup(x); } int sta[xn],top; void rever(int x) { if(!rev[x])return; rev[c[x][0]]^=1; rev[c[x][1]]^=1; swap(c[x][0],c[x][1]); rev[x]=0; } void splay(int x) { sta[top=1]=x; for(int i=x;!isroot(i);i=fa[i])sta[++top]=fa[i];//i! for(int i=top;i;i--)rever(sta[i]); while(!isroot(x)) { int y=fa[x],z=fa[y]; if(!isroot(y)) ((c[y][0]==x)^(c[z][0]==y))?rotate(x):rotate(y); rotate(x); } } void access(int x) { for(int t=0;x;c[x][1]=t,pushup(x),t=x,x=fa[x])splay(x);//pushup } void makeroot(int x) { access(x); splay(x); rev[x]^=1; } int find(int x) { access(x); splay(x); while(c[x][0])x=c[x][0]; return x; } void link(int x,int y) { makeroot(x); fa[x]=y; } void cut(int x,int y) { makeroot(x); access(y); splay(y); fa[x]=0; c[y][0]=0; pushup(y); } db dfs(int x,db v) { db ret=cal(x,v); if(c[x][0])ret+=dfs(c[x][0],v); if(c[x][1])ret+=dfs(c[x][1],v); return ret; } void query1(int x,int y,db v) { if(find(x)!=find(y)){puts("unreachable"); return;} makeroot(x); access(y); splay(y); db ret=0; //for(int t=x;t!=fa[y];t=fa[t])ret+=cal(t,v); //printf("%.8e ",ret); printf("%.8e ",dfs(y,v)); } void query2(int x,int y) { if(find(x)!=find(y)){puts("unreachable"); return;} makeroot(x); access(y); splay(y); printf("%.8e ",sum[y]); } int main() { n=rd(); m=rd(); scanf("%s",tp); for(int i=1;i<=n;i++)f[i]=rd(),scanf("%lf%lf",&A[i],&B[i]); for(int i=1,u,v;i<=m;i++) { scanf("%s",op); if(op[0]=='a'){u=rd()+1; v=rd()+1; link(u,v);} else if(op[0]=='d'){u=rd()+1; v=rd()+1; cut(u,v);} else if(op[0]=='m'){int x=rd()+1; access(x); splay(x); f[x]=rd(); scanf("%lf%lf",&A[x],&B[x]); pushup(x);}//a,s,p else { u=rd()+1; v=rd()+1; db x; scanf("%lf",&x); if(tp[1]=='0')query2(u,v); else query1(u,v,x); } } }
参考了博客：https://www.cnblogs.com/zhoushuyu/p/8148732.html
A[x] 写成 A[i] 看了一个小时...
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; typedef double db; int rd() { int ret=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return f?ret:-ret; } int const xn=1e5+5; int n,m,f[xn],fa[xn],c[xn][2],jc[15],rev[xn]; db A[xn],B[xn],g[xn][15]; char tp[10],op[15]; bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;} db t[5]; void pushup(int x) { db p=1; if(f[x]==1) { t[0]=sin(B[x]); t[1]=cos(B[x]); t[2]=-t[0]; t[3]=-t[1]; for(int i=0;i<=12;i++,p=p*A[x]) g[x][i]=p*t[i%4]+g[c[x][0]][i]+g[c[x][1]][i]; } if(f[x]==2) { db tmp=exp(B[x]); for(int i=0;i<=12;i++,p=p*A[x]) g[x][i]=p*tmp+g[c[x][0]][i]+g[c[x][1]][i]; } if(f[x]==3) { g[x][0]=B[x]+g[c[x][0]][0]+g[c[x][1]][0]; g[x][1]=A[x]+g[c[x][0]][1]+g[c[x][1]][1]; for(int i=2;i<=12;i++)g[x][i]=g[c[x][0]][i]+g[c[x][1]][i]; } } void rotate(int x) { int y=fa[x],z=fa[y],d=(c[y][1]==x); if(!isroot(y))c[z][c[z][1]==y]=x; fa[x]=z; fa[y]=x; fa[c[x][!d]]=y; c[y][d]=c[x][!d]; c[x][!d]=y; pushup(y); pushup(x); } int sta[xn],top; void rever(int x) {if(!rev[x])return; rev[c[x][0]]^=1; rev[c[x][1]]^=1; swap(c[x][0],c[x][1]); rev[x]=0;} void splay(int x) { sta[top=1]=x; for(int i=x;!isroot(i);i=fa[i])sta[++top]=fa[i]; for(int i=top;i;i--)rever(sta[i]); while(!isroot(x)) { int y=fa[x],z=fa[y]; if(!isroot(y)) ((c[y][0]==x)^(c[z][0]==y))?rotate(x):rotate(y); rotate(x); } } void access(int x) { for(int t=0;x;c[x][1]=t,pushup(x),t=x,x=fa[x])splay(x); } void makeroot(int x) { access(x); splay(x); rev[x]^=1; } int find(int x) { access(x); splay(x); while(c[x][0])x=c[x][0]; return x; } void link(int x,int y) { makeroot(x); fa[x]=y; } void cut(int x,int y) { makeroot(x); access(y); splay(y); fa[x]=c[y][0]=0; pushup(y); } void query(int x,int y,db v) { if(find(x)!=find(y)){puts("unreachable"); return;} makeroot(x); access(y); splay(y); db ret=0,p=1; for(int i=0;i<=12;i++,p=p*v)ret+=g[y][i]*p/jc[i]; printf("%.8e ",ret); } int main() { n=rd(); m=rd(); scanf("%s",tp); for(int i=1;i<=n;i++)f[i]=rd(),scanf("%lf%lf",&A[i],&B[i]); jc[0]=1; for(int i=1;i<=12;i++)jc[i]=jc[i-1]*i; for(int i=1,u,v;i<=m;i++) { scanf("%s",op); if(op[0]=='a'){u=rd()+1; v=rd()+1; link(u,v);} if(op[0]=='d'){u=rd()+1; v=rd()+1; cut(u,v);} if(op[0]=='m'){int x=rd()+1; splay(x); f[x]=rd(); scanf("%lf%lf",&A[x],&B[x]); pushup(x);}//A[x] not A[i]! if(op[0]=='t'){u=rd()+1; v=rd()+1; db x; scanf("%lf",&x); query(u,v,x);} } return 0; }