Solution

这个才是真的"树套树"嘛

题目看上去就很暴力，而实现起来更暴力

• 加进去的子树显然看成一个点，在建一棵新的树
• 两个树都要树剖
• 因为涉及到在原树上找点的问题，而我们知道一个点在某个子树内的排名，所以只好用主席树了

注意会爆long long！

因为调到生无可恋，只好加了这句

#define int long long

Code 

#include
    
     #define ll long long#define int long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline ll read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define reg register#define MN 100005//模板树中的操作 struct edge{int to,nex;}e[MN<<1];int hr[MN],en;inline void ins(int f,int t){    e[++en]=(edge){t,hr[f]};hr[f]=en;    e[++en]=(edge){f,hr[t]};hr[t]=en;}int N,deep[MN],par[MN],Top[MN],Siz[MN],Mx[MN],dfn[MN],fdfn[MN],dind;inline void dfs1(int x,int f){    deep[x]=deep[par[x]=f]+1;Siz[x]=1;    for(reg int i=hr[x];i;i=e[i].nex)if(f^e[i].to)        dfs1(e[i].to,x),Siz[e[i].to]>Siz[Mx[x]]?Mx[x]=e[i].to:0,Siz[x]+=Siz[e[i].to];}inline void dfs2(int x,int tp){    dfn[x]=++dind;fdfn[dind]=x;Top[x]=tp;if(Mx[x]) dfs2(Mx[x],tp);    for(reg int i=hr[x];i;i=e[i].nex)if((par[x]^e[i].to)&&(Mx[x]^e[i].to))        dfs2(e[i].to,e[i].to);}inline ll Getdis(int x,int y){    ll res=deep[x]+deep[y];    while(Top[x]^Top[y])    {        if(deep[Top[x]]>deep[Top[y]]) x=par[Top[x]];        else y=par[Top[y]];    }    return res-2*min(deep[x],deep[y]);}#define mid ((l+r)>>1)int sz,t[MN*20],ls[MN*20],rs[MN*20],rt[MN];void Modify(int &rt,int ori,int l,int r,int x){    rt=++sz;ls[rt]=ls[ori];rs[rt]=rs[ori];t[rt]=t[ori]+1;    if(l==r) return;    if(x<=mid) Modify(ls[rt],ls[ori],l,mid,x);    else Modify(rs[rt],rs[ori],mid+1,r,x);}inline int init(){    for(reg int i=1;i<=N;++i) Modify(rt[i],rt[i-1],1,N,fdfn[i]);}inline int Query(int rt1,int rt2,int l,int r,int k){    if(l==r) return l;    if(t[ls[rt2]]-t[ls[rt1]]>=k) return Query(ls[rt1],ls[rt2],l,mid,k);    else return Query(rs[rt1],rs[rt2],mid+1,r,k-(t[ls[rt2]]-t[ls[rt1]]));}inline int point(int k,int x){    return Query(rt[dfn[x]-1],rt[dfn[x]+Siz[x]-1],1,N,k);}#undef mid//鲲树的操作int root[MN],M;ll a[MN],from[MN];edge E[MN<<1];int En,Hr[MN];inline void Ins(int f,int t){    E[++En]=(edge){t,Hr[f]};Hr[f]=En;    E[++En]=(edge){f,Hr[t]};Hr[t]=En;}inline int get(ll x){return std::lower_bound(a+1,a+M+2,x)-a;}inline int getrk(ll x,int y){return x-a[y-1];}int dep[MN],siz[MN],mx[MN],top[MN],fa[MN];ll dis_tp[MN];inline void Dfs1(int x,int f){    dep[x]=dep[fa[x]=f]+1,siz[x]=1;    for(reg int i=Hr[x];i;i=E[i].nex)if(f^E[i].to)        Dfs1(E[i].to,x),siz[E[i].to]>siz[mx[x]]?mx[x]=E[i].to:0,siz[x]+=siz[E[i].to];}inline void Dfs2(int x,int tp){    if(x==tp) dis_tp[x]=0;    else dis_tp[x]=1ll*dis_tp[fa[x]]+1ll+1ll*deep[from[x]]-1ll*deep[root[fa[x]]];    top[x]=tp;    if(mx[x]) Dfs2(mx[x],tp);    for(reg int i=Hr[x];i;i=E[i].nex)if((fa[x]^E[i].to)&&(mx[x]^E[i].to))        Dfs2(E[i].to,E[i].to);}void que(ll x,ll y){    int X=get(x),Y=get(y);    if(X==Y)    {        std::cout<
     
      <
      
       dep[top[Y]])        {            ans+=1ll*(deep[x]-deep[root[X]]);            ans+=1ll*dis_tp[X]+1ll;x=from[top[X]];X=fa[top[X]];        }        else        {            ans+=1ll*(deep[y]-deep[root[Y]]);            ans+=1ll*dis_tp[Y]+1ll;y=from[top[Y]];Y=fa[top[Y]];        }    }    if(dep[X]^dep[Y])    {        if(dep[X]>dep[Y]) ans+=1ll*dis_tp[X]-1ll*dis_tp[Y]+1ll*(deep[x]-deep[root[X]])-1ll*(deep[from[mx[Y]]]-deep[root[Y]]),x=from[mx[Y]];        else ans+=1ll*dis_tp[Y]-1ll*dis_tp[X]-1ll*(deep[from[mx[X]]]-deep[root[X]])+1ll*(deep[y]-deep[root[Y]]),y=from[mx[X]];    }    ans+=1ll*Getdis(x,y);std::cout<
       
        <
       
      
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！