4539: [Hnoi2016]树
Time Limit: 40 Sec
Memory Limit: 256 MB
Submit: 479
Solved: 183
[
Submit][
Status][
Discuss]
Description
小A想做一棵很大的树，但是他手上的材料有限，只好用点小技巧了。开始，小A只有一棵结点数为N的树，结 点的编号为1,2,…,N，其中结点1为根；我们称这颗树为模板树。小A决定通过这棵模板树来构建一颗大树。构建过 程如下：（1）将模板树复制为初始的大树。（2）以下(2.1)(2.2)(2.3)步循环执行M次（2.1）选择两个数字a,b， 其中1<=a<=N，1<=b<=当前大树的结点数。（2.2）将模板树中以结点a为根的子树复制一遍，挂到大树中结点b的下 方(也就是说，模板树中的结点a为根的子树复制到大树中后，将成为大树中结点b的子树)。（2.3）将新加入大树 的结点按照在模板树中编号的顺序重新编号。例如，假设在进行2.2步之前大树有L个结点，模板树中以a为根的子 树共有C个结点，那么新加入模板树的C个结点在大树中的编号将是L+1,L+2,…,L+C；大树中这C个结点编号的大小 顺序和模板树中对应的C个结点的大小顺序是一致的。下面给出一个实例。假设模板树如下图：
根据第(1)步，初始的大树与模板树是相同的。在(2.1)步，假设选择了a=4，b=3。运行(2.2)和(2.3)后，得到新的 大树如下图所示 现在他想问你，树中一些结点对的距离是多少。
Input
第一行三个整数：N,M,Q，以空格隔开，N表示模板树结点数，M表示第(2)中的循环操作的次数，Q 表示询问数 量。接下来N-1行，每行两个整数 fr,to，表示模板树中的一条树边。再接下来M行，每行两个整数x,to，表示将模 板树中 x 为根的子树复制到大树中成为结点to的子树的一次操作。再接下来Q行，每行两个整数fr,to，表示询问 大树中结点 fr和 to之间的距离是多少。N,M,Q<=100000
Output
输出Q行，每行一个整数，第 i行是第 i个询问的答案。
Sample Input
5 2 3 1 4 1 3 4 2 4 5 4 3 3 2 6 9 1 8 5 3
Sample Output
6 3 3
HINT
经过两次操作后，大树变成了下图所示的形状： 结点6到9之间经过了6条边，所以距离为6；类似地，结点1到8之间经过了3条边；结点5到3之间也经过了3条边。
Source
[
Submit][
Status][
Discuss]
题目已经给定了一棵模板树，无论怎样的添加都是新增模板树的某个子树
采用离散化的思想，，对于每次新增的子树，只保留它的根节点，这样将大树缩成一棵新树
这么做剩余节点是O(n)的，在上面可以随意进行LCA等操作
现在考虑两个点之间的询问
假设有办法快速处理新树上两个点之间的距离，新树中某个节点对应的原树中那个子树里两个节点的距离
那么，两个点的询问(x,y)，假设x在新树中属于节点p1，y属于p2
首先，x走到p1，y走到p2，然后求出p1,p2的lca，p1走到lca中某个点,p2走到lca中某个点
说某个点，其实就是在p到lca的路径上第一个属于lca代表子树的点
最后这两个点再走一下统计答案
特判lca与p1，p2重合的三种情况。。询问就解决了
然后要处理距离的统计问题
新树上的距离倍增一下就好了
然后是新树中某个节点对应子树里两个点的距离
这两个点对应回模板树里的点，然后直接在模板树求距离就行了，再次倍增==
对应的话，可以转化为在某个子树中询问第k小
主席树 + dfs序解决
代码略长，，O(nlogn)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
const int maxn = 1E5 + 10;
const int T = 20;
typedef long long LL;
struct data{
LL x,y; data(){}
data(LL x,LL y): x(x),y(y){}
}D[maxn];
LL cnt,Root[maxn],f2[maxn][20],dis[maxn][20],L2[maxn],F[maxn];
int n,m,Q,Cnt,tot,dfs_clock,siz[maxn],dfn[maxn],rt[maxn],Num[maxn]
,c[maxn*T],lc[maxn*T],rc[maxn*T],f1[maxn][20],L1[maxn];
vector <int> v[maxn];
vector <int> v2[maxn];
int Insert(int o,int l,int r,int pos)
{
int ret = ++Cnt;
c[ret] = c[o] + 1;
if (l == r) return ret;
int mid = (l + r) >> 1;
if (pos <= mid) lc[ret] = Insert(lc[o],l,mid,pos),rc[ret] = rc[o];
else rc[ret] = Insert(rc[o],mid+1,r,pos),lc[ret] = lc[o];
return ret;
}
void Dfs1(int x,int from)
{
dfn[x] = ++dfs_clock; siz[x] = 1;
rt[dfs_clock] = Insert(rt[dfs_clock-1],1,n,x);
for (int i = 1; i < 20; i++) f1[x][i] = f1[f1[x][i-1]][i-1];
for (int i = 0; i < v[x].size(); i++)
{
int to = v[x][i];
if (to == from) continue;
L1[to] = L1[x] + 1; f1[to][0] = x;
Dfs1(to,x); siz[x] += siz[to];
}
}
bool Judge(int k,LL B) {return D[k].x <= B && B <= D[k].y;}
int Search(int L,int R,LL B)
{
while (R - L > 1)
{
int mid = (L + R) >> 1;
if (Judge(mid,B)) return mid;
if (D[mid].y < B) L = mid;
else R = mid;
}
return (Judge(L,B))?L:R;
}
int Sum(int o1,int o2,int l,int r,int pos)
{
if (r <= pos) return c[o2] - c[o1];
int mid = (l + r) >> 1,ret = 0;
ret += Sum(lc[o1],lc[o2],l,mid,pos);
if (pos > mid) ret += Sum(rc[o1],rc[o2],mid+1,r,pos);
return ret;
}
LL LCA1(int x,int y)
{
LL ret = 0;
if (L1[x] < L1[y]) swap(x,y);
for (int j = 19; j >= 0; j--)
if (L1[x] - (1<<j) >= L1[y])
ret += (1<<j),x = f1[x][j];
if (x == y) return ret;
for (int j = 19; j >= 0; j--)
if (f1[x][j] != f1[y][j])
{
x = f1[x][j]; y = f1[y][j];
ret += (1<<(j+1));
}
return ret + 2;
}
int LCA2(int x,int y)
{
if (L2[x] < L2[y]) swap(x,y);
for (int j = 19; j >= 0; j--)
if (L2[x] - (1<<j) >= L2[y])
x = f2[x][j];
if (x == y) return y;
for (int j = 19; j >= 0; j--)
if (f2[x][j] != f2[y][j])
x = f2[x][j],y = f2[y][j];
return f2[x][0];
}
int GetNum(int o1,int o2,int l,int r,int k)
{
if (l == r) return l;
int mid = (l + r) >> 1,lef = c[lc[o2]] - c[lc[o1]];
if (lef >= k) return GetNum(lc[o1],lc[o2],l,mid,k);
else return GetNum(rc[o1],rc[o2],mid+1,r,k - lef);
}
LL Dis(LL x,LL y,int p)
{
int A = GetNum(rt[dfn[Num[p]]-1],rt[dfn[Num[p]]+siz[Num[p]]-1],1,n,x-D[p].x+1);
int B = GetNum(rt[dfn[Num[p]]-1],rt[dfn[Num[p]]+siz[Num[p]]-1],1,n,y-D[p].x+1);
return LCA1(A,B);
}
LL Dis2(int &p,int goal)
{
LL ret = 0;
for (int j = 19; j >= 0; j--)
if (L2[f2[p][j]] > L2[goal])
{
ret += dis[p][j];
p = f2[p][j];
}
p = F[p];
return ret + 1LL;
}
void Dfs2(int x)
{
for (int i = 1; i < 20; i++)
{
f2[x][i] = f2[f2[x][i-1]][i-1];
if (!f2[x][i]) break;
dis[x][i] = dis[f2[x][i-1]][i-1] + dis[x][i-1];
}
for (int i = 0; i < v2[x].size(); i++)
{
int to = v2[x][i];
L2[to] = L2[x] + 1; f2[to][0] = x;
dis[to][0] = Dis(F[to],Root[x],x) + 1LL;
Dfs2(to);
}
}
LL getLL()
{
char ch = getchar(); LL ret = 0;
while (ch < '0' || '9' < ch) ch = getchar();
while ('0' <= ch && ch <= '9')
ret = ret*10LL + 1LL*(ch - '0'),ch = getchar();
return ret;
}
int main()
{
#ifdef DMC
freopen("DMC.txt","r",stdin);
#endif
n = getLL(); m = getLL(); Q = getLL();
for (int i = 1; i < n; i++)
{
int x = getLL(),y = getLL();
v[x].push_back(y);
v[y].push_back(x);
}
L1[1] = 1; Dfs1(1,0); cnt = n;
D[tot = 1] = data(1,n); Num[1] = Root[1] = 1;
for (int i = 1; i <= m; i++)
{
int a = getLL(); LL b = getLL();
int pos = Search(1,tot,b);
int rk = Sum(rt[dfn[a]-1],rt[dfn[a]+siz[a]-1],1,n,a);
Root[++tot] = cnt + 1LL*rk;
v2[pos].push_back(tot);
F[tot] = b; Num[tot] = a;
D[tot] = data(cnt + 1LL,cnt + 1LL*siz[a]);
cnt += 1LL*siz[a];
}
L2[1] = 1; Dfs2(1);
while (Q--)
{
LL x = getLL(),y = getLL(),Ans = 0;
int p1 = Search(1,tot,x);
int p2 = Search(1,tot,y);
int lca = LCA2(p1,p2);
if (p1 == p2) Ans = Dis(x,y,lca);
else if (lca != p1 && lca != p2)
{
Ans += Dis(x,Root[p1],p1) + Dis(y,Root[p2],p2);
Ans += Dis2(p1,lca) + Dis2(p2,lca);
Ans += Dis(p1,p2,lca);
}
else
{
if (lca == p2) swap(p1,p2),swap(x,y);
Ans += Dis(y,Root[p2],p2) + Dis2(p2,lca);
Ans += Dis(x,p2,lca);
}
printf("%lld\n",Ans);
}
return 0;
}
