P3248 [HNOI2016]树
斯德哥尔摩
2018-07-20 21:04:45
[P3248 [HNOI2016]树](https://www.luogu.org/problemnew/show/P3248)
### 先说一点题外话
这题前前后后卡了我4天。。。
第一天卡在了$WA$的暴力上，后三天卡在了$RE$的正解上。。。
简直药丸啊。。。
$HNOI2016$除了[P3247 [HNOI2016]最小公倍数](https://www.luogu.org/problemnew/show/P3247)，就属这题最毒了。。。
### 步入正题
你见过真正的树套树吗？
没错，这题就是一个真正的树套树！
什么线段树套$Splay$，树状数组套$Treap$，主席树套替罪羊树等等一大堆乱七八糟的树套树，都没有这题强！
因为这是一颗**大树套小树**！
外面一颗巨大的树，树的每个节点又是一棵小树。。。
无从下手，怎么办？
那就拆成几个操作，一个一个分析：
#### 树的形态
我们先把原来的模板树建出来，倍增$LCA$直接上。
那大树怎么办？
如果把所有的节点都建出来，一共$10^{10}$个，不但$TLE$，而且$MLE$。。。
从上面提到的大树的每个节点又是一棵小树可知：
我们可以对每一棵小树缩点，只保留根节点，然后再在大树上跑$LCA$！
现在我们需要在缩好点的树上维护树上距离。
由于我们在映射的时候只留下了$root$，因此我们现在只需要保证两个root在大树上的距离和在缩点之后的树上距离是一样的即可。
所以大树的每一条边，都有**边权**！
两个$root$的之间边权就是在执行复制操作时，大树上$to$节点到自己$root$的距离$+1$。
同时我们再定义一个$val[i]$表示点i在大树上的真实父亲的在模板树上的编号，这里的$i$表示缩点之后树上的编号而不是原来大树的编号。
那么这个缩完点之后的树，一个节点代表着一棵树，所以对于一个大树原来的节点$to$，我们可以用一个二元组$(y,x)$唯一表示它，$y$就是这个节点的$y$，而$x$代表了它的所在的子树缩点后在树上的编号$x$。
#### 树上距离
首先我们的思路是：两个节点$u,v$跳到自己的缩点之后的根节点，之后再跳到缩点树上的$LCA$。
但此时我们发现这样走的不是最短路，重复走的部分是两个节点跳到$LCA$内部之后，在$LCA$所对应树的里的$LCA$深度的$2$倍。
#### 建树
1. 读入$u(int),v(long long)$
2. 将$v$转换为$(y,x)$的二元组形式
3. 查找$y$到$x.root$的在膜板树上距离$val$
4. 新建一个缩点树节点$newnode$，在$newnode$和$x$之间连一条边权为$val+1$的边
5. $newnode$的$val$属性记为$y$
#### 求距离
1. 读入$u,v$
2. 将$u,v$转换为$(y_1,x_1),(y_2,x_2)$的二元组形式
3. 查找$x_1,x_2$的$LCA-lca$，并且记录$h_1,h_2$两个点
然而，$h_1,h_2$因$x_1,x_2$在树上的关系而不同：
1. 如果$x_1==x_2$,那么$h_1=y_1,h_2=y_2$
2. 如果$x_1$与$x_2$是直系祖先关系，且$x_1$是祖先，那么$h_1=y_1$，$h_2=x_1$儿子中是$x_2$祖先的那个点的$val$属性
3. 其他情况
$h_1=lca$儿子中是$x_1$祖先的那个点的$val$属性；
$h_2=lca$儿子中是$x_2$祖先的那个点的$val$属性
不难发现，在每一种情况下，$h_1,h_2$都是$u,v$跳到同一个小树以后所在的节点，而这个小树在缩点树上对应着点$lca$
4. 查找$y_1$与$x_1.root$的距离
5. 查找$y_2$与$x_2.root$的距离
6. 查找$x_1,x_2$间的距离
7. 查找$h_1,h_2$的$LCA$和$lca.root$的距离
8. 将4,5,6步中的距离加起来再减去2倍的7步中查到的距离就是答案了。
#### 编号转换
发现$x$值相同的点编号是一段连续的区间，于是我们可以开一个$right$数组记录每个$x$值所对应的最大大树编号，也就只是记录$x$的区间右端点编号.
此时我们可以通过$lower\underline\ bound$求出这个编号的$x$值。
通过这个点和区间右端点编号的差我们可以算出来这个点在$x.root$的子树中的排名，现在我们要求$y$，也就是求子树第$k$大。
此时我们通过$dfs$序把子树转换为一段区间，这样问题变成了求静态区间第$k$小，去吧，主席树！
好了我们用$log_2n$的复杂度（以及巨大的代码量。。。）实现了映射。
#### 查距离
树上倍增找$LCA$，直接算距离：
$$dis(u,v)=dis(u,root)+dis(v,root)-dis(lca,root)* 2$$
#### 查找$h_1,h_2$
啊!这是一个辣手的操作。。。
但是我们首先可以大力特判掉$u==v$的情形。
接下来还记得树上倍增的过程吗？
如果$u$和$v$不是直系祖先关系，那么循环结束时$u,v$的父亲才是$lca$，此时的$u,v$一定是原来$u,v$的的祖先，同时也是$lca$的儿子 所以直接取$val$属性就行了
下面是最辣手的情况，$u$和$v$是直系祖先关系：
我们在将$u,v$跳到深度相等的操作改为$u$比$v$的深度低1，由于特判掉了$u==v$，所以我们总是可以查到那个是$lca$儿子又是$u$祖先的点，取这个点的$val$属性就好了。
于是，一个疯狂魔改后的超级NB天下无双的倍增$LCA$就这样诞生了！
### 后记
这题真的毒。。。
我大概为$WA$的提交贡献了10+次。。。
我不停地找标程，不停地对拍，不停地输出中间结果，然后发现：
我竟然把大树中的节点个数当成了$n$！
然后改成了节点个数$c-1$，就过了。
**就过了！**
好尴尬啊。。。
附上恶心到$namespace$封装也挡不住他的毒性的丧心病狂的的代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define MAXN 100010
using namespace std;
int n,m,q,c=1;
int id[MAXN],pos[MAXN],tree_size[MAXN];
inline long long read(){
long long date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
namespace ST{//小树
int d=1,e=1;
int head[MAXN],deep[MAXN],f[MAXN][20];
struct Tree{
int next,to;
}a[MAXN<<1];
inline void add(int x,int y){
a[d].to=y;a[d].next=head[x];head[x]=d++;
a[d].to=x;a[d].next=head[y];head[y]=d++;
}
void buildtree(int rt){
tree_size[rt]=1;
id[rt]=e;pos[e++]=rt;
for(int i=head[rt];i;i=a[i].next){
int will=a[i].to;
if(!deep[will]){
deep[will]=deep[rt]+1;
f[will][0]=rt;
buildtree(will);
tree_size[rt]+=tree_size[will];
}
}
}
void step(){
for(int i=1;i<=19;i++)
for(int j=1;j<=n;j++)
f[j][i]=f[f[j][i-1]][i-1];
}
int LCA(int x,int y){//正常倍增LCA
if(deep[x]<deep[y])swap(x,y);
for(int i=19;i>=0;i--)if(deep[f[x][i]]>=deep[y])x=f[x][i];
if(x==y)return x;
for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}
return f[x][0];
}
inline long long dis(int x,int y){return abs(deep[x]-deep[y]);}
inline long long dis_lca(int x,int y,int rt){return deep[LCA(x,y)]-deep[rt];}
}
namespace CT{//主席树
int d=1,size=1,root[MAXN];
struct Charman_Tree{
int l,r,sum;
}a[MAXN*22];
struct Right{
int root,x;
long long v;
friend bool operator <(const Right p,const Right q){return p.v<q.v;}
}right[MAXN];
void insert(int k,int l,int r,int &rt){//正常静态区间第k大
a[size]=a[rt];rt=size++;
a[rt].sum++;
if(l==r)return;
int mid=l+r>>1;
if(k<=mid)insert(k,l,mid,a[rt].l);
else insert(k,mid+1,r,a[rt].r);
}
int query(int i,int j,int l,int r,int k){
if(l==r)return l;
int mid=l+r>>1,t=a[a[j].l].sum-a[a[i].l].sum;
if(k<=t)return query(a[i].l,a[j].l,l,mid,k);
else return query(a[i].r,a[j].r,mid+1,r,k-t);
}
inline void buildtree(){//对pos[i]建主席树
root[0]=0;
a[0].l=a[0].r=a[0].sum=0;
for(int i=1;i<=n;i++){
root[i]=root[i-1];
insert(pos[i],0,n,root[i]);
}
}
inline int kth(int l,int r,int k){return query(root[l],root[r],0,n,k);}
inline void insert_node(int root,int x){
right[d]=(Right){root,x,right[d-1].v+tree_size[root]};
d++;
}
inline void query_node(long long v,int &root,int &y,int &x){
Right p=*lower_bound(right+1,right+d,(Right){0,0,v});
root=p.root;x=p.x;
int rank=v+tree_size[root]-p.v;
y=kth(id[root]-1,id[root]+tree_size[root]-1,rank);
}
}
namespace BT{//大树
int d=1,head[MAXN],deep[MAXN],val[MAXN],f[MAXN][20];
long long dis[MAXN];
struct Tree{
int next,to;
long long w;
}a[MAXN<<1];
inline void add(int u,int v,long long w){
a[d].to=v;a[d].w=w;a[d].next=head[u];head[u]=d++;
a[d].to=u;a[d].w=w;a[d].next=head[v];head[v]=d++;
}
void buildtree(int rt){
int will;
for(int i=head[rt];i;i=a[i].next){
will=a[i].to;
if(!deep[will]){
deep[will]=deep[rt]+1;
dis[will]=dis[rt]+a[i].w;
f[will][0]=rt;
buildtree(will);
}
}
}
void step(){
for(int i=1;i<=19;i++)
for(int j=1;j<=c-1;j++)//就是这里！坑。。。
f[j][i]=f[f[j][i-1]][i-1];
}
int LCA(int x,int y,int &u,int &v){//魔改LCA
if(x==y)return x;
if(deep[x]<deep[y]){swap(x,y);swap(u,v);}
for(int i=19;i>=0;i--)if(deep[f[x][i]]>deep[y])x=f[x][i];
if(f[x][0]==y){u=val[x];return y;}
else if(deep[x]!=deep[y])x=f[x][0];
for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}
u=val[x];v=val[y];
return f[x][0];
}
inline long long dist(int u,int v,int lca){return dis[u]+dis[v]-dis[lca]*2;}
}
inline void solve(long long x,long long y){//求大树上距离
long long dist;
int r1,x1,y1,h1;int r2,x2,y2,h2;
CT::query_node(x,r1,y1,x1);CT::query_node(y,r2,y2,x2);
h1=y1;h2=y2;
int lca=BT::LCA(x1,x2,h1,h2),r=CT::right[lca].root;
dist=ST::dis(r1,y1)+ST::dis(r2,y2)-ST::dis_lca(h1,h2,r)*2+BT::dist(x1,x2,lca);
printf("%lld\n",dist);
}
void work(){//工作
long long x,y;
while(q--){
x=read();y=read();
solve(x,y);
}
}
void init(){//读入+建树
int x,y,rt;
n=read();m=read();q=read();
for(int i=1;i<n;i++){
x=read();y=read();
ST::add(x,y);
}
ST::deep[1]=1;
ST::buildtree(1);
ST::step();
CT::buildtree();
CT::insert_node(1,c++);
for(int i=1;i<=m;i++){
int u=read();
long long v=read();
CT::query_node(v,rt,y,x);
CT::insert_node(u,c);
BT::val[c]=y;
int w=ST::dis(y,rt)+1;
BT::add(x,c,w);
c++;
}
BT::deep[1]=1;BT::dis[1]=0;
BT::buildtree(1);
BT::step();
}
int main(){//主函数So easy!
init();
work();
return 0;
}
```