Description:
给定一棵n个点的"模板树",同时要你维护一棵"大树",一开始"大树"为"模板树"
有m次操作,为把模板树中的一个节点及其子树接到"大树"中的一个节点下方,同时按原来编号相对大小顺序重新编号
然后有q个询问,询问大树中两个点的距离
Hint:
(n,m,q le 10^5)
Solution:
第一眼,wc这不是个水题吗,建个虚点随便搞一下
什么?要维护节点编号,主席树随便搞一下
After coding...... 给细节跪了,毒瘤题惹不起惹不起
这是我见过细节最多的数据结构题? 虽然思路很好想
主要是各种节点映射,分类讨论比较烦,详见代码:
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mxn=5e5+5;
ll n,m,Q,cnt,hd[mxn];
inline ll read() {
char c=getchar(); ll x=0,f=1;
while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
return x*f;
}
inline void chkmax(ll &x,ll y) {if(x<y) x=y;}
inline void chkmin(ll &x,ll y) {if(x>y) x=y;}
struct ed {
ll to,nxt;
}t[mxn<<1];
namespace CT {
ll tot,rt[mxn],sz[mxn<<6],ls[mxn<<6],rs[mxn<<6];
void update(ll las,ll &p,ll l,ll r,ll val) {
if(!p) p=++tot; sz[p]=sz[las]+1;
if(l==r) return ; ll mid=(l+r)>>1;
if(val<=mid) update(ls[las],ls[p],l,mid,val),rs[p]=rs[las];
else update(rs[las],rs[p],mid+1,r,val),ls[p]=ls[las];
}
ll query(ll las,ll p,ll l,ll r,ll rk) {
if(l==r) return l;
ll mid=(l+r)>>1; ll tp=sz[ls[p]]-sz[ls[las]];
if(rk<=tp) return query(ls[las],ls[p],l,mid,rk);
else return query(rs[las],rs[p],mid+1,r,rk-tp);
}
}
namespace TpTr {
ll n,idx,tot;
ll f[mxn][25],dep[mxn],qu[mxn],S[mxn],T[mxn],lk[mxn],son[mxn*2],nxt[mxn];
void add(ll x,ll y) {
++tot; son[tot]=y; nxt[tot]=lk[x]; lk[x]=tot;
}
void build(ll u,ll fa) {
S[u]=++idx; qu[idx]=u; f[u][0]=fa; dep[u]=dep[fa]+1;
for(ll i=1;i<=24;++i) f[u][i]=f[f[u][i-1]][i-1];
for(ll i=lk[u];i;i=nxt[i])
if(son[i]!=fa) build(son[i],u);
T[u]=idx;
}
void buildCT() {
for(ll i=1;i<=n;++i)
CT::update(CT::rt[i-1],CT::rt[i],1,n,qu[i]);
}
void input() {
ll u,v;
for(ll i=1;i<n;++i) {
u=read(); v=read();
add(u,v); add(v,u);
}
build(1,0); buildCT();
}
ll getdis(ll u,ll v) {
ll res=0;
if(dep[u]<dep[v]) swap(u,v);
for(ll i=24;i>=0;--i)
if(dep[f[u][i]]>=dep[v]) res+=(1<<i),u=f[u][i];
for(ll i=24;i>=0;--i)
if(f[u][i]!=f[v][i])
res+=(1<<(i+1)),u=f[u][i],v=f[v][i];
if(u==v) return res;
else return res+2;
}
}
namespace BigTr {
ll n,m,f[mxn][25],dep[mxn],pre[mxn];
ll cnt,dis[mxn][25],S[mxn],T[mxn],lk[mxn];
ll getrt(ll u) {
ll l=1,r=n;
while(l<=r) {
ll mid=(l+r)>>1;
S[mid]<=u?l=mid+1:r=mid-1; //二分查找求出"根"节点,比较巧妙
} //之前还愚蠢的打了个动态开点线段树
return r;
}
ll getpre(ll u) {
ll rt=getrt(u);
return CT::query(CT::rt[TpTr::S[pre[rt]]-1],CT::rt[TpTr::T[pre[rt]]],1,TpTr::n,u-S[rt]+1);
}
void build() {
n=1; dep[1]=1; pre[1]=1; S[1]=1; T[1]=TpTr::n; cnt=T[1];
for(ll i=1;i<=m;++i) {
ll fr=read(); ll to=read(); ll rt=getrt(to);
++n; dep[n]=dep[rt]+1; lk[n]=to; pre[n]=fr;
S[n]=cnt+1; T[n]=cnt+TpTr::T[fr]-TpTr::S[fr]+1;
cnt=T[n]; f[n][0]=rt;
dis[n][0]=TpTr::dep[getpre(to)]-TpTr::dep[pre[rt]]+1;
// 小树接到一个节点上,要算出正确深度后接到该节点的"根"下
// 这样会破坏正确的父子关系
// 所以在solve函数里需要分类讨论一下
for(ll j=1;j<=24;++j)
f[n][j]=f[f[n][j-1]][j-1],dis[n][j]=dis[n][j-1]+dis[f[n][j-1]][j-1];
}
}
ll solve(ll u,ll v) {
ll res=0; ll rtu=getrt(u),rtv=getrt(v);
if(rtu==rtv) return TpTr::getdis(getpre(u),getpre(v)); //分类讨论.1
if(dep[rtu]<dep[rtv]) swap(u,v),swap(rtu,rtv);
res+=TpTr::dep[getpre(u)]-TpTr::dep[pre[rtu]];
u=rtu;
for(ll i=24;i>=0;--i)
if(dep[f[u][i]]>dep[rtv]) //为什么是">"号呢?就是要判断是否是上面所述的那种情况
res+=dis[u][i],u=f[u][i];
if(getrt(lk[u])==rtv) return res+1+TpTr::getdis(getpre(lk[u]),getpre(v)); //分类讨论.2
res+=TpTr::dep[getpre(v)]-TpTr::dep[pre[rtv]];
v=rtv;
if(dep[u]>dep[v]) res+=dis[u][0],u=f[u][0];
for(ll i=24;i>=0;--i)
if(f[u][i]!=f[v][i])
res+=dis[u][i]+dis[v][i],u=f[u][i],v=f[v][i];
u=lk[u],v=lk[v],res+=2;
return res+TpTr::getdis(getpre(u),getpre(v)); //分类讨论.3
}
}
int main()
{
TpTr::n=read(); BigTr::m=read(); Q=read();
TpTr::input(); BigTr::build();
while(Q--) printf("%lld
",BigTr::solve(read(),read()));
return 0;
}