显然是动态树裸题：O(mlogn)
#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=100010; int sumv[maxn],val[maxn],pre[maxn],fa[maxn],ch[maxn][2],flip[maxn]; void maintain(int x) {sumv[x]=sumv[ch[x][0]]+sumv[ch[x][1]]+val[x];} void pushdown(int x) { if(!flip[x]) return; flip[ch[x][0]]^=1;flip[ch[x][1]]^=1; swap(ch[x][0],ch[x][1]);flip[x]=0; } void rotate(int x,int d) { pushdown(x);int y=pre[x],z=pre[y]; pre[ch[x][d]]=y;ch[y][d^1]=ch[x][d]; pre[x]=z;ch[z][ch[z][1]==y]=x; pre[y]=x;ch[x][d]=y;maintain(y); } void splay(int x) { int rt=x;while(pre[rt]) rt=pre[rt]; if(rt!=x) { fa[x]=fa[rt];fa[rt]=0; while(pre[x]) pushdown(pre[x]),rotate(x,ch[pre[x]][0]==x); maintain(x); } else pushdown(x); } void access(int x) { for(int y=0;x;x=fa[x]) { splay(x);pre[ch[x][1]]=0;fa[ch[x][1]]=x; ch[x][1]=y;pre[y]=x;fa[y]=0; maintain(x);y=x; } } int findrt(int x) { access(x);splay(x); while(ch[x][0]) x=ch[x][0];return x; } void makeroot(int x) {access(x);splay(x);flip[x]^=1;} void link(int x,int y) {makeroot(x);fa[x]=y;} void query(int x,int y) {makeroot(x);access(y);splay(y);printf("%d ",sumv[y]);} int main() { int n=read(); for(int i=1;i<=n;i++) val[i]=read(); int m=read(); while(m--) { char cmd=getchar();while(!isalpha(cmd)) cmd=getchar(); int x=read(),y=read(); if(cmd=='e') { if(findrt(x)==findrt(y)) query(x,y); else puts("impossible"); } else { if(findrt(x)==findrt(y)) puts("no"); else link(x,y),puts("yes"); } } return 0; }
可以写个启发式合并O(mlog^2n)
#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=100010; int first[maxn],next[maxn*2],to[maxn*2],e; void AddEdge(int u,int v) { to[++e]=v;next[e]=first[u];first[u]=e; to[++e]=u;next[e]=first[v];first[v]=e; } int val[maxn],pa[maxn],s[maxn]; inline int findset(int x) {return pa[x]==x?x:pa[x]=findset(pa[x]);} int fa[maxn][12],sum[maxn],dep[maxn]; void dfs(int x) { sum[x]=sum[fa[x][0]]+val[x];dep[x]=dep[fa[x][0]]+1; for(int i=1;i<12;i++) fa[x][i]=fa[fa[x][i-1]][i-1]; for(int i=first[x];i;i=next[i]) if(to[i]!=fa[x][0]) fa[to[i]][0]=x,dfs(to[i]); } void query(int x,int y) { int ret=sum[x]+sum[y],lca; if(dep[x]<dep[y]) swap(x,y); for(int i=11;i>=0;i--) if((1<<i)<=dep[x]-dep[y]) x=fa[x][i]; for(int i=11;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; lca=(x==y)?x:fa[x][0]; printf("%d ",ret-sum[lca]-sum[fa[lca][0]]); } int main() { int n=read(); for(int i=1;i<=n;i++) sum[i]=val[i]=read(),pa[i]=i,s[i]=1; int m=read(); while(m--) { char cmd=getchar();while(!isalpha(cmd)) cmd=getchar(); int x=read(),y=read(); if(cmd=='e') { int p1=findset(x),p2=findset(y); if(x==y) printf("%d ",val[x]); else if(p1==p2) query(x,y); else puts("impossible"); } else if(cmd=='b') { int p1=findset(x),p2=findset(y); if(p1==p2) {puts("no");continue;}puts("yes"); if(s[p1]>s[p2]) swap(p1,p2),swap(x,y); pa[p1]=p2;s[p2]+=s[p1];fa[x][0]=y;AddEdge(x,y); dfs(x); } } return 0; }