「HNOI2016」树
事毒瘤题...
我一开始以为每次把大树的子树再接给大树，然后死活不知道咋做，心想怕不是个神仙题哦
然后看题解后才发现是把模板树的子树给大树，虽然思维上难度没啥了，但是还是很难写的。
大值思路是对每个子树维护成一个大节点，存一些根啊，深度啊，到大节点根距离啊，节点编号范围啊之类的信息。
然后发现维护相对节点标号大小是个区间第k大，得对dfs序建一颗主席树
然后每次询问倍增跳一跳，讨论个几种情况之类的。
ps:别吐槽名字
Code:
#include <cstdio>
#include <cctype>
#include <algorithm>
#define int long long
const int N=1e5+10;
template <class T>
void read(T &x)
{
x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
int n,m,q;
namespace koito_yuu
{
int head[N],to[N<<1],Next[N<<1],cnt;
void add(int u,int v)
{
to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;
}
int f[18][N],dep[N],dfn[N],ha[N],siz[N],clock;
void dfs(int now)
{
ha[dfn[now]=++clock]=now;
dep[now]=dep[f[0][now]]+1;
siz[now]=1;
for(int i=1;f[i-1][now];i++) f[i][now]=f[i-1][f[i-1][now]];
for(int v,i=head[now];i;i=Next[i])
if((v=to[i])!=f[0][now])
f[0][v]=now,dfs(v),siz[now]+=siz[v];
}
int LCA(int x,int y)
{
if(dep[x]<dep[y]) std::swap(x,y);
for(int i=17;~i;i--)
if(dep[f[i][x]]>=dep[y])
x=f[i][x];
if(x==y) return x;
for(int i=17;~i;i--)
if(f[i][x]!=f[i][y])
x=f[i][x],y=f[i][y];
return f[0][x];
}
int getdis(int x,int y)
{
int lca=LCA(x,y);
return dep[x]+dep[y]-(dep[lca]<<1);
}
int ch[N*30][2],sum[N*30],root[N],tot;
#define ls ch[now][0]
#define rs ch[now][1]
#define ols ch[las][0]
#define ors ch[las][1]
void rebuild(int &now,int las,int l,int r,int p)
{
now=++tot;
if(l==r) {++sum[now];return;}
int mid=l+r>>1;
if(p<=mid) rebuild(ls,ols,l,mid,p),rs=ors;
else ls=ols,rebuild(rs,ors,mid+1,r,p);
sum[now]=sum[ls]+sum[rs];
}
int query(int now,int las,int l,int r,int k)
{
if(l==r) return l;
int mid=l+r>>1;
if(sum[ls]-sum[ols]>=k) return query(ls,ols,l,mid,k);
else return query(rs,ors,mid+1,r,k-(sum[ls]-sum[ols]));
}
void work()
{
for(int u,v,i=1;i<n;i++) read(u),read(v),add(u,v),add(v,u);
dfs(1);
for(int i=1;i<=n;i++) rebuild(root[i],root[i-1],1,n,ha[i]);
}
}
using koito_yuu::siz;
using koito_yuu::dfn;
using koito_yuu::getdis;
namespace nanami_touko
{
int num,L[N],R[N],f[18][N],dis[N],root[N],dep[N],par[N];
void query(int x,int &whi,int &pos,int &rt)
{
whi=std::lower_bound(R+1,R+1+num,x)-R;
rt=root[whi];
pos=koito_yuu::query(koito_yuu::root[dfn[rt]+siz[rt]-1],koito_yuu::root[dfn[rt]-1],1,n,x-L[whi]+1);
}
int LCA(int x,int y)
{
if(dep[x]<dep[y]) std::swap(x,y);
for(int i=17;~i;i--)
if(dep[f[i][x]]>=dep[y])
x=f[i][x];
if(x==y) return x;
for(int i=17;~i;i--)
if(f[i][x]!=f[i][y])
x=f[i][x],y=f[i][y];
return f[0][x];
}
int clim(int x,int y)
{
for(int i=17;~i;i--)
if(dep[f[i][x]]>dep[y])
x=f[i][x];
return x;
}
void work()
{
root[++num]=1;
dep[num]=1,L[num]=1,R[num]=n;
for(int x,t,i=1;i<=m;i++)//子树x复制到t的儿子
{
read(x),read(t);
root[++num]=x;
L[num]=R[num-1]+1,R[num]=L[num]+siz[x]-1;
int pos,whi,rt;
query(t,whi,pos,rt);//t在哪个大节点,t在模板树的编号和大节点的根
par[num]=pos;
f[0][num]=whi,dis[num]=getdis(rt,pos)+1+dis[whi];
dep[num]=dep[whi]+1;
for(int j=1;f[j-1][num];j++) f[j][num]=f[j-1][f[j-1][num]];
}
}
}
using nanami_touko::root;
using nanami_touko::dis;
using nanami_touko::clim;
using nanami_touko::par;
namespace saeki_sayaka
{
int get(int a,int b,int c,int d,int ru,int rv)
{
return getdis(a,b)+dis[ru]-dis[rv]+getdis(c,d)+1;
}
void work()
{
for(int u,v,i=1;i<=q;i++)
{
read(u),read(v);
int whiu,rtu,whiv,rtv;
nanami_touko::query(u,whiu,u,rtu);
nanami_touko::query(v,whiv,v,rtv);
if(whiu==whiv)
{
printf("%lld\n",getdis(u,v));
continue;
}
if(nanami_touko::dep[whiu]<nanami_touko::dep[whiv])
std::swap(whiu,whiv),std::swap(u,v),std::swap(rtu,rtv);
int lca=nanami_touko::LCA(whiu,whiv);
if(lca==whiv)
{
int ancu=clim(whiu,lca);
printf("%lld\n",get(u,rtu,par[ancu],v,whiu,ancu));
continue;
}
int ancu=clim(whiu,lca),ancv=clim(whiv,lca);
int urt=par[ancu],vrt=par[ancv];
int p=koito_yuu::LCA(urt,vrt);
printf("%lld\n",get(u,rtu,urt,p,whiu,ancu)+get(v,rtv,vrt,p,whiv,ancv));
}
}
}
signed main()
{
read(n),read(m),read(q);
koito_yuu::work();
nanami_touko::work();
saeki_sayaka::work();
return 0;
}
2019.3.11