题解 SP4155 【OTOCI - OTOCI】

双倍经验P4312

这是一道LCT模板题，但因为没有删除操作，我们可以使用树剖+树状数组通过。

那如何加边呢？

因为没有要求强制在线，我们可以使用并查集维护。

时间复杂度 $O(nlo{g}^{2}n)$，因为树状数组常数极小，可以通过本题。

#include <bits/stdc++.h>
#define il inline
using namespace std;
const int N=3e5+10;
int n,m;
int head[N],to[N*2],nxt[N*2],cnt=1;
void link(int u,int v){
  to[cnt]=v;
  nxt[cnt]=head[u];
  head[u]=cnt++;
}//加边
int fa[N],dep[N],siz[N],son[N],top[N],seg[N],rev[N],tot;
int f[N],t[N],v[N],x[N],y[N],op[N];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}//并查集
il void add(int x,int y){for(int i=x;i<=n;i+=i&-i) t[i]+=y;}
il int sum(int x){int s=0;for(int i=x;i;i-=i&-i) s+=t[i];return s;}//树状数组
void dfs1(int x,int f,int d){
   dep[x]=d; fa[x]=f; siz[x]=1;
   int maxson=-1;
   for(int i=head[x];i;i=nxt[i]){
      int y=to[i];
      if(y==f) continue;
      dfs1(y,x,d+1);
      siz[x]+=siz[y];
      if(siz[y]>maxson) son[x]=y,maxson=siz[y];
   }
}
void dfs2(int x,int topf){
   seg[x]=++tot;
   rev[tot]=v[x];
   top[x]=topf;
   if(!son[x]) return;
   dfs2(son[x],topf);
   for(int i=head[x];i;i=nxt[i]){
      int y=to[i];
      if(y==fa[x]||y==son[x]) continue;
      dfs2(y,y);
   }
}//树剖
int main(){
   ios::sync_with_stdio(0);
   cin>>n;
   for(int i=1;i<=n;i++) cin>>v[i],f[i]=i;
   cin>>m;
   for(int i=1;i<=m;i++){
      char s[10];cin>>s>>x[i]>>y[i];
      if(s[0]=='b') op[i]=0;
      else if(s[0]=='p') op[i]=1;
      else if(s[0]=='e') op[i]=2;
      if(op[i]==2&&find(x[i])!=find(y[i])) op[i]=4;
      if(op[i]==0&&find(x[i])!=find(y[i])) 
         link(x[i],y[i]),link(y[i],x[i]),f[f[x[i]]]=f[y[i]],op[i]=3;
   }//离线处理
   for(int i=1;i<=n;i++) if(!fa[i]) dfs1(i,0,1);
   for(int i=1;i<=n;i++) {if(!seg[i])dfs2(i,i);add(seg[i],v[i]);} 
   for(int i=1;i<=m;i++)
      if(op[i]==0) cout<<"no"<<endl;
      else if(op[i]==1) add(seg[x[i]],y[i]-sum(seg[x[i]])+sum(seg[x[i]]-1));//加上y-x
      else if(op[i]==3) cout<<"yes"<<endl;
      else if(op[i]==4) cout<<"impossible"<<endl;
      else{
         int s=0,a=x[i],b=y[i];
         while(top[a]!=top[b]){
            if(dep[top[a]]<dep[top[b]]) swap(a,b);
            s+=sum(seg[a])-sum(seg[top[a]]-1),a=fa[top[a]];
         }
         if(seg[a]>seg[b]) swap(a,b);
         cout<<s+sum(seg[b])-sum(seg[a]-1)<<endl;
      }
   return 0;
}