Luogu

BZOJ

分析

码题。

显然大树最多会有 $10^{10}$ 个点,完全开不下。

但是发现每次操作都是复制一颗子树,所以可以把大树当做一颗树套树

构造大树时,令每一个大节点为模板树中的一颗子树,并对大树重新编号,就像这样(图源网络,侵删):

作出如下定义:

  • 两个大节点的边权为对应的树的根节点的距离,比如上图$1$和$2$之间的边权为$2$。
  • $st[i]$ 表示大节点 $i$ 对应的小节点的编号区间的起点,如 $st[1]=1$,$st[2]=6$。
  • $ed[i]$ 表示大节点 $i$ 对应的小节点的编号区间的终点,如 $ed[1]=5$,$ed[2]=8$。
  • $pre[i]$ 表示大节点 $i$ 对应的是模板树中哪一个节点的子树,如 $pre[1]=1$,$pre[2]=4$。
  • $lnk[i]$ 表示大节点 $i$ 挂在哪一个节点下面,如$lnk[2]=3$,$lnk[3]=2$。

这些信息都很容易求出。

再定义如下函数:

  • $get\_root(x)$ :查找小节点 $x$ 所在的大节点。因为 $st$ 是递增的,所以只要二分就可以确定。
  • $get\_pre(x)$:查找小节点 $x$ 在模板树中对应的节点。假设 $x$ 在大节点 $y$ 中,我们只要找到 $y$ 对应的树中第 $x-st[y]+1$ 小的节点即可。这个可以用主席树实现。

现在来考虑怎么算答案。

主要思想是,先跳到大节点对应的子树的根节点,再在大树上跳到同一个大节点内,再在该大节点对应的子树内跳到同一个小节点,然后沿途累加距离。

这个过程和求$\mathrm{LCA}$非常像,然而细节比较多,写代码时要注意。

具体实现及细节见代码。

代码

如有不适请自行格式化。

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline ll read() {
    ll X=0; int w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

struct president_tree {
    struct node { int lc,rc,sum; };
    node t[N*20];
    int rt[N],tot;

    president_tree() { this->tot=0; }
    
    inline int build(int l,int r) {
        int p=++tot; t[p].sum=0;
        if (l==r) return p;
        int mid=(l+r)>>1;
        t[p].lc=build(l,mid),t[p].rc=build(mid+1,r);
        return p;
    }
    
    inline int insert(int now,int l,int r,int x) {
        int p=++tot; t[p]=t[now],++t[p].sum;
        if (l==r) return p;
        int mid=(l+r)>>1;
        if (x<=mid) t[p].lc=insert(t[p].lc,l,mid,x);
        else t[p].rc=insert(t[p].rc,mid+1,r,x);
        t[p].sum=t[t[p].lc].sum+t[t[p].rc].sum;
        return p;
    }
    
    inline int query(int p,int q,int l,int r,int k) {
        if (l==r) return l;
        int mid=(l+r)>>1;
        int dlt=t[t[q].lc].sum-t[t[p].lc].sum;
        if (k<=dlt) return query(t[p].lc,t[q].lc,l,mid,k);
        else return query(t[p].rc,t[q].rc,mid+1,r,k-dlt);
    }
} T;

namespace template_tree {
    struct Edge { int v,nxt; } e[N<<1];
    int head[N],cnt=0;

    inline void addEdge(int u,int v) {
        e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
    }

    int n,dfs_clock=0;
    int f[20][N],dep[N],st[N],ed[N],pos[N],sz[N];

    inline void dfs(int u,int fa) {
        dep[u]=dep[fa]+1,f[0][u]=fa,st[u]=++dfs_clock,pos[dfs_clock]=u;
        for (re int i=1;i<=16;++i) f[i][u]=f[i-1][f[i-1][u]];
        for (re int i=head[u];i;i=e[i].nxt)
            if (e[i].v!=fa) dfs(e[i].v,u);
        ed[u]=dfs_clock,sz[u]=ed[u]-st[u]+1;
    }

    inline void build_president_tree() {
        T.rt[0]=T.build(1,n);
        for (re int i=1;i<=n;++i) T.rt[i]=T.insert(T.rt[i-1],1,n,pos[i]);
    }

    inline void build() {
        for (re int i=1;i<n;++i) {
            int u=read(),v=read();
            addEdge(u,v),addEdge(v,u);
        }
        dfs(1,0); build_president_tree();
    }

    inline int get_lca(int u,int v) {
        if (dep[u]<dep[v]) swap(u,v);
        for (re int i=16;i>=0;i--)
            if (dep[f[i][u]]>dep[v]) u=f[i][u];
        if (dep[u]!=dep[v]) u=f[0][u];
        for (re int i=16;i>=0;i--)
            if (f[i][u]!=f[i][v]) u=f[i][u],v=f[i][v];
        if (u!=v) u=f[0][u],v=f[0][v];
        return u;
    }
    
    inline int get_dis(int u,int v) {
        int w=get_lca(u,v);
        return dep[u]+dep[v]-2*dep[w];
    }
}

namespace big_tree {
    int n,m; ll tot;
    int f[20][N],dep[N],pre[N];
    ll dis[20][N],st[N],ed[N],lnk[N];
    
    inline int get_root(ll u) {
        int L=1,R=n;
        while (L<=R) {
            int mid=(L+R)>>1;
            if (st[mid]<=u) L=mid+1;
            else R=mid-1;
        }
        return R;
    }

    inline int get_pre(ll u) {
        int rt=get_root(u);
        return T.query(T.rt[template_tree::st[pre[rt]]-1],T.rt[template_tree::ed[pre[rt]]],1,template_tree::n,u-st[rt]+1);
    }
    
    inline void build() {
        n=dep[1]=pre[1]=st[1]=1,tot=ed[1]=template_tree::n;
        for (re int i=1;i<=m;++i) {
            ll u=read(),v=read(); int rt=get_root(v);
            dep[++n]=dep[rt]+1,lnk[n]=v,pre[n]=u;
            st[n]=tot+1,ed[n]=tot+template_tree::sz[u],tot=ed[n];
            f[0][n]=rt,dis[0][n]=template_tree::dep[get_pre(v)]-template_tree::dep[pre[rt]]+1;
            for (re int j=1;j<=16;++j)
                f[j][n]=f[j-1][f[j-1][n]],dis[j][n]=dis[j-1][n]+dis[j-1][f[j-1][n]];
        }
    }

    inline ll calc_ans(ll u,ll v) {
        int fu=get_root(u),fv=get_root(v);
        if (fu==fv) return template_tree::get_dis(get_pre(u),get_pre(v));
        if (dep[fu]<dep[fv]) swap(u,v),swap(fu,fv);
        ll ans=template_tree::dep[get_pre(u)]-template_tree::dep[pre[fu]]; u=fu;
        for (re int i=16;i>=0;--i)
            if (dep[f[i][u]]>dep[fv]) ans+=dis[i][u],u=f[i][u];
        if (get_root(lnk[u])==fv)
            return ans+1+template_tree::get_dis(get_pre(lnk[u]),get_pre(v));
        ans+=template_tree::dep[get_pre(v)]-template_tree::dep[pre[fv]]; v=fv;
        if (dep[u]>dep[v]) ans+=dis[0][u],u=f[0][u];
        for (re int i=16;i>=0;--i)
            if (f[i][u]!=f[i][v]) ans+=dis[i][u]+dis[i][v],u=f[i][u],v=f[i][v];
        return ans+2+template_tree::get_dis(get_pre(lnk[u]),get_pre(lnk[v]));
    }
}

int Q;

int main() {
    template_tree::n=read(),big_tree::m=read(),Q=read();
    template_tree::build(); big_tree::build();
    while (Q--) {
        ll u=read(),v=read();
        printf("%lld\n",big_tree::calc_ans(u,v));
    }
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 18 PM