题解 P3302 【[SDOI2013]森林】
IC_QQQ
2019-06-05 11:17:12
### 树上的主席树（利用LCA）+启发式合并
有兴趣的可以去看看简化版（去掉连边操作）题目[P2633 Count on a tree](https://www.luogu.org/problemnew/show/P2633)。~~获得双倍经验~~。
这道题主要有两个操作：
1. 求路径 **（u，v）** 上第**k**小点。
2. 在点 **x,y** 间连一条无向边。
第一个操作很明显，在树上建立主席树，主席树 **i** 维护从根节点 **root** 到点 **i** 路径上所有点的信息。
查询路径 **（u，v）** 上第**k**小点也容易想到，需要用到 **LCA** 。
我们找到 **（u，v）** 的最近公共祖先 **lca** 和 **lca** 的父节点 **fa_lca** 。维护这四个点的信息进行查询就可以了。
对于第二个操作，为了使时间更优，我们需要用到启发式合并的思想。~~启发式合并听上去玄妙无比，其实很普通~~。简而言之就是记录每棵树的大小，连边时把小树连接到大树上去，重构小树中的主席树、**LCA**相关数组。
~~其他的一些操作像离散化大家都会吧。~~
### 真正的重点—关于这道题的特性：
在无数次 **RE** 第**2,3,6**个测试点后，我终于找到了坑点：问题出在 **LCA** 上。
下面是错误示范：（**ans[i][j]** 表示 **i** 的 **2^j** 级祖先）
```cpp
void update_LCA(int u,int fa){
deep[u]=deep[fa]+1;ans[u][0]=fa;
for(int i=1;i<=lg[deep[u]];i++)//这里的上界
ans[u][i]=ans[ans[u][i-1]][i-1];
for(int i=head[u];i;i=nxt[i])
if(to[i]!=fa) update_LCA(to[i],u);
return;
}
```
只需要这里把循环的上界从 **lg[deep[u]]** 改为 **x** ，保证 **2^x>=n** 就可以了，比如 **18,19**等等。
为什么会这样，**lg[deep[u]]** 不是 **LCA** 的通用写法吗，**LCA** 的模板题也是写的**lg[deep[u]]**。
我翻讨论区，发现也有人困惑于此。~~然而，题解都巧妙地回避了这个问题，没有解答~~。
无奈，我下载了第**2**个测试点的数据，开始了漫长的探索之路。
终于，在数据中第**16058**次操作（询问操作），我发现了问题。
**lg[deep[u]]** 的确是 **LCA** 的通用写法，没有问题，这道题上行不通是这道题的 **特性** ，因为这道题有一个特殊的操作：**连边** 。
我们来看 **get_LCA** 操作：
```cpp
int get_LCA(int u,int v){
if(deep[u]<deep[v]) swap(u,v);
while(deep[u]>deep[v])
u=ans[u][lg[deep[u]-deep[v]]];
if(u==v) return u;
for(int i=lg[deep[u]];i>=0;i--)
if(ans[u][i]!=ans[v][i])//重点
u=ans[u][i],v=ans[v][i];
return ans[u][0];
}
```
如果我们连边重构 **update_LCA** 时采用 **lg[deep[u]]** ，可能存在一种情况：这个点 **i** 原本的 **ans[i][j]**，**j** 最大已经大于了 **lg[deep[u]]** （即原来深度更深），但是我们更新只是更新到 **lg[deep[u]]** ，它上面的状态没有改变。在执行 **get_LCA** ，进行判断时：
```cpp
if(ans[u][i]!=ans[v][i])//重点
u=ans[u][i],v=ans[v][i];
```
本来，这一次 **u,v** 不能被改变， 由于状态没有全部更新，**u,v** 被改变了，导致**lca**找错，进而答案错误，下一次进行异或操作时数字变得很大，数组越界直接导致 **RE** 。
举个栗子大家就知道了：
假设 **ans[x]={root,6},ans[y]={root,7}**。
从 **u,v** 出发，模拟走一遍。
**i=2**时，**u**跳到了**x**。**v**跳到了**y**。
**i=1**时，**x**跳到了**6**，**v**跳到了**7**。
好了，已经出错了。
这就是这道题的特性，连边重构 **update_LCA** 时，上界很重要。
~~至于为什么其他题上界可以是 **lg[deep[u]]** ，大家自己想想吧，不难。~~
### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=8e4+5;
int T,n,m,TT,last;
int tot,row[N],s[N],size[N];
int cnt,to[4*N],nxt[4*N],head[4*N];
int from[N],lg[N],ans[N][35],deep[N];
struct Tree{
int ls,rs,si;
}t[105*N];
int root[N],top;
int in(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){ if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
void adds(int x,int y){
to[++cnt]=y;nxt[cnt]=head[x];head[x]=cnt;
return;
}
void pre_work(){
int a,b;lg[0]=-1;
T=in();n=in();m=in();TT=in();
for(int i=1;i<=n;i++)
row[i]=s[i]=in(),lg[i]=lg[i>>1]+1,from[i]=i;
sort(row+1,row+1+n);
tot=unique(row+1,row+1+n)-(row+1);
for(int i=1;i<=n;i++)
s[i]=lower_bound(row+1,row+1+tot,s[i])-row;
for(int i=1;i<=m;i++)
a=in(),b=in(),adds(a,b),adds(b,a);
return;
}
void built(int &pos,int pre,int l,int r,int wi){
t[pos=++top]=t[pre];
t[pos].si++;
if(l==r) return;
int mid=(l+r)>>1;
if(wi<=mid) built(t[pos].ls,t[pre].ls,l,mid,wi);
else built(t[pos].rs,t[pre].rs,mid+1,r,wi);
return;
}
void dfs(int u,int fa,int rt){
built(root[u],root[fa],1,tot,s[u]);
deep[u]=deep[fa]+1;ans[u][0]=fa;
size[rt]++;from[u]=rt;
for(int i=1;i<=18;i++)
ans[u][i]=ans[ans[u][i-1]][i-1];
for(int i=head[u];i;i=nxt[i])
if(to[i]!=fa) dfs(to[i],u,rt);
return;
}
int get_LCA(int u,int v){
if(deep[u]<deep[v]) swap(u,v);
while(deep[u]>deep[v])
u=ans[u][lg[deep[u]-deep[v]]];
if(u==v) return u;
for(int i=lg[deep[u]];i>=0;i--)
if(ans[u][i]!=ans[v][i])
u=ans[u][i],v=ans[v][i];
return ans[u][0];
}
int Answer(int u,int v,int og,int fg,int l,int r,int k){
if(l==r) return row[l];
int sum=t[t[u].ls].si+t[t[v].ls].si-t[t[og].ls].si-t[t[fg].ls].si;
int mid=(l+r)>>1;
if(k<=sum) return Answer(t[u].ls,t[v].ls,t[og].ls,t[fg].ls,l,mid,k);
return Answer(t[u].rs,t[v].rs,t[og].rs,t[fg].rs,mid+1,r,k-sum);
}
int main(){
pre_work();
for(int i=1;i<=n;i++)
if(from[i]==i) dfs(i,0,i);
char ch[5];int x,y,k;
for(int i=1;i<=TT;i++){
scanf("%s",ch);x=in()^last;y=in()^last;
if(ch[0]=='Q'){
k=in()^last;
int og=get_LCA(x,y),fg=ans[og][0];
last=Answer(root[x],root[y],root[og],root[fg],1,tot,k);
printf("%d\n",last);
}
else{
adds(x,y);adds(y,x);
int fx=from[x],fy=from[y];
if(size[fy]<size[fx]) dfs(y,x,fx);
else dfs(x,y,fy);
}
}
return 0;
}
```