BZOJ 4539: [Hnoi2016]树
小 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
Solution
先对模板树求 lca，并按 dfs 序建一棵主席树。
每次向大树上加子树时，先二分查找他的父亲在哪一块，然后在主席树上查接到哪个节点下面。
对于每一块，存它的根节点与根节点的父亲在模板树中的编号。
然后把每一块视做节点，可以得到一棵大树，对大树也求 lca。
处理查询时，需要分 3 种情况：在同一块中，两块在一条链上，两块不在一条链上。
Code
#include<bits/stdc++.h>
typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
#define xx first
#define yy second
template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline void repr(T &a,T b){if(a<b)a=b;}
template<typename T> inline void repl(T &a,T b){if(a>b)a=b;}
template<typename T> inline T sqr(T x){return x*x;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define lb(x) ((x)&(-(x)))
#define N 100000
namespace zx
{
struct node
{
int lc,rc,cnt;
}s[2000000];
int sm=1;
int modify(int x,int l,int r,int p)
{
int t=sm++;
s[t]=s[x];
s[t].cnt++;
if(l^r)
{
int f=(l+r)>>1;
if(p<=f)
s[t].lc=modify(s[x].lc,l,f,p);
else
s[t].rc=modify(s[x].rc,f+1,r,p);
}
return t;
}
int kth(int a,int b,int l,int r,int k)
{
if(l==r)return l;
int t=s[s[a].lc].cnt-s[s[b].lc].cnt,f=(l+r)>>1;
if(t>=k)return kth(s[a].lc,s[b].lc,l,f,k);
return kth(s[a].rc,s[b].rc,f+1,r,k-t);
}
int root[N+1];
}
int n,m,q;
namespace t1
{
int p[N+1],idm,id[N+1],idr[N+1],fa[N+1][17],dep[N+1],sz[N+1];
struct edge
{
int to,ne;
}e[N<<1];
inline void add(int x,int a,int b)
{
e[x].to=b,e[x].ne=p[a],p[a]=x;
}
void dfs(int x)
{
sz[x]=1;
id[x]=++idm;
zx::root[id[x]]=zx::modify(zx::root[id[x]-1],1,n,x);
for(int i=p[x];i;i=e[i].ne)
if(e[i].to^fa[x][0])
fa[e[i].to][0]=x,dep[e[i].to]=dep[x]+1,dfs(e[i].to),sz[x]+=sz[e[i].to];
idr[x]=idm;
}
inline int dis(int x,int y)
{
int a=x,b=y,ret=0;
if(dep[a]<dep[b])
{
for(int i=16;~i;i--)
if((dep[b]-dep[a])&(1<<i))
ret+=1<<i,b=fa[b][i];
}
else if(dep[a]>dep[b])
{
for(int i=16;~i;i--)
if((dep[a]-dep[b])&(1<<i))
ret+=1<<i,a=fa[a][i];
}
if(a==b)return ret;
for(int i=16;~i;i--)
if(fa[a][i]^fa[b][i])
a=fa[a][i],b=fa[b][i],ret+=1<<i+1;
return ret+2;
}
}
namespace t2
{
int cnt=1;
ll id[N+1],nid;
struct data
{
int a,b,dep,fa[17],di[17];
}s[N+1];
inline void link(int a,ll b)
{
int c=std::upper_bound(id,id+cnt,b)-id-1;
int cf=s[c].a,d=zx::kth(zx::root[t1::idr[cf]],zx::root[t1::id[cf]-1],1,n,b-id[c]+1);
s[cnt].a=a;
s[cnt].b=d;
s[cnt].dep=s[c].dep+1;
s[cnt].fa[0]=c;
s[cnt].di[0]=t1::dis(cf,d)+1;
id[cnt]=nid;
nid+=t1::sz[a];
cnt++;
}
inline void init()
{
for(int i=0;i<16;i++)
for(int j=0;j<cnt;j++)
s[j].fa[i+1]=s[s[j].fa[i]].fa[i],s[j].di[i+1]=s[j].di[i]+s[s[j].fa[i]].di[i];
}
inline int lca(int x,int y)
{
int a=x,b=y;
if(s[a].dep<s[b].dep)
{
for(int i=16;~i;i--)
if((s[b].dep-s[a].dep)&(1<<i))
b=s[b].fa[i];
}
else if(s[a].dep>s[b].dep)
{
for(int i=16;~i;i--)
if((s[a].dep-s[b].dep)&(1<<i))
a=s[a].fa[i];
}
if(a==b)return a;
for(int i=16;~i;i--)
if(s[a].fa[i]^s[b].fa[i])
a=s[a].fa[i],b=s[b].fa[i];
return s[a].fa[0];
}
inline ll linkdis(int p,int q,int x,int y)
{
ll ret=t1::dis(x,s[p].a)+1;
for(int i=16;~i;i--)
if((s[p].dep-s[q].dep-1)&(1<<i))
ret+=s[p].di[i],p=s[p].fa[i];
return ret+t1::dis(s[p].b,y);
}
inline ll dis(ll x,ll y)
{
int p=std::upper_bound(id,id+cnt,x)-id-1,q=std::upper_bound(id,id+cnt,y)-id-1;
int xid=zx::kth(zx::root[t1::idr[s[p].a]],zx::root[t1::id[s[p].a]-1],1,n,x-id[p]+1);
int yid=zx::kth(zx::root[t1::idr[s[q].a]],zx::root[t1::id[s[q].a]-1],1,n,y-id[q]+1);
if(p==q)return t1::dis(xid,yid);
int t=lca(p,q);
if(t==p)return linkdis(q,p,yid,xid);
if(t==q)return linkdis(p,q,xid,yid);
ll ret=t1::dis(xid,s[p].a)+t1::dis(yid,s[q].a)+2;
for(int i=16;~i;i--)
if((s[p].dep-s[t].dep-1)&(1<<i))
ret+=s[p].di[i],p=s[p].fa[i];
for(int i=16;~i;i--)
if((s[q].dep-s[t].dep-1)&(1<<i))
ret+=s[q].di[i],q=s[q].fa[i];
return ret+t1::dis(s[p].b,s[q].b);
}
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
t1::add(i<<1,a,b);
t1::add(i<<1|1,b,a);
}
zx::root[0]=zx::sm++;
t1::fa[1][0]=1;
t1::dfs(1);
for(int i=0;i<16;i++)
for(int j=1;j<=n;j++)
t1::fa[j][i+1]=t1::fa[t1::fa[j][i]][i];
t2::s[0].a=1;
t2::id[0]=1;
t2::nid=n+1;
while(m--)
{
int a;
ll b;
scanf("%d%lld",&a,&b);
t2::link(a,b);
}
t2::init();
while(q--)
{
ll a,b;
scanf("%lld%lld",&a,&b);
printf("%lld\n",t2::dis(a,b));
}
}
日期： 2016-12-16
这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/149/ 查看。