题解 P4219 【[BJOI2014]大融合】

· · 题解

题目大意：给定 n 个点，要求支持两种操作 m 次：

  1. A x y，加入一条边 (x,y)，保证图的形态始终是森林。
  2. Q x y，查询经过边 (x,y) 的路径数量，保证 (x,y) 存在于当前的树中。

数据范围：

怎么大家都是什么 LCT 树链剖分线段树的，树状数组 dfs 序它不香咩。

首先很容易想到，我们只需要维护每个点当前的根和当前的子树大小就可以很容易做这道题了。

然后就是怎么维护的问题，我们可以先离线建出加入所有边后的树（森林），那么根可以用并查集维护，子树大小可以用树状数组 + dfs 序来维护。

具体的，对于一条边 (x,y)，假设 y 是 x 的父亲。若是加入这条边，那么我们需要将 (y,rot_y) 这条链加上 siz_x，并将 x 子树中所有点的根设为 rot_y；若是查询，则答案为：

siz_x(siz_{rot_{y}}-siz_x)

这之中涉及的所有操作均可用并查集和树状数组 + dfs 序解决。

什么？怎么用树状数组 + dfs 序维护这个东西？

对于链加操作，我们在 y 处加上 siz_x，在 fa_{rot_y} 处减去 siz_x，那么在查询的时候就变成了查询子树和，接下来就是 dfs 序 + 数据结构维护的经典操作了。

时间复杂度 O(n+m\log n)。

代码如下：

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N=100000;

int n,cq,qopt[N+9],qx[N+9],qy[N+9];
struct side{
  int y,next;
}e[N*2+9];
int lin[N+9],cs;

void Ins(int x,int y){e[++cs].y=y;e[cs].next=lin[x];lin[x]=cs;}
void Ins2(int x,int y){Ins(x,y);Ins(y,x);}

void into(){
  scanf("%d%d",&n,&cq);
  for (int i=1;i<=cq;++i){
    char opt[2];
    scanf("%s%d%d",opt,&qx[i],&qy[i]);
    if (!(qopt[i]=opt[0]=='Q')) Ins2(qx[i],qy[i]);
  }
}

int fa[N+9],ld[N+9],rd[N+9],co;

void Dfs_ord(int k,int fat){
  fa[k]=fat;
  ld[k]=++co;
  for (int i=lin[k];i;i=e[i].next)
    if (e[i].y^fat) Dfs_ord(e[i].y,k);
  rd[k]=co;
}

void Get_ord(){
  for (int i=1;i<=n;++i)
    if (!ld[i]) Dfs_ord(i,0);
}

struct union_find_set{
  int fa[N+9];
  int &operator [] (const int &p){return fa[p];}
  void Build(){for (int i=1;i<=n;++i) fa[i]=i;}
  int Query_fa(int k){return k^fa[k]?fa[k]=Query_fa(fa[k]):k;}
}uni;

int c[N+9];

void Add(int p,int v){if (!p) return;for (;p<=n;p+=p&-p) c[p]+=v;}
int Query(int p){int res=0;for (;p;p-=p&-p) res+=c[p];return res;}
int Query(int l,int r){return Query(r)-Query(l-1);}

LL ans[N+9];

void Get_ans(){
  uni.Build();
  for (int i=1;i<=n;++i) Add(ld[i],1),Add(ld[fa[i]],-1);
  for (int i=1;i<=cq;++i){
    int x=qx[i],y=qy[i];
    if (ld[x]<ld[y]) swap(x,y);
    int fy=uni.Query_fa(y),t=Query(ld[x],rd[x]);
    if (qopt[i]) ans[i]=(LL)t*(Query(ld[fy],rd[fy])-t);
    else Add(ld[y],t),Add(ld[fa[uni[x]=fy]],-t);
  }
}

void work(){
  Get_ord();
  Get_ans();
}

void outo(){
  for (int i=1;i<=cq;++i)
    if (qopt[i]) printf("%lld\n",ans[i]);
}

int main(){
  into();
  work();
  outo();
  return 0;
}