【题解】LOJ 2050 「HNOI2016」树

请注意,本文编写于 98 天前,最后修改于 98 天前,其中某些信息可能已经过时。

Problem

给定一个模板树,第一次将其完全复制,接下来每次取模板树的一个子树连在当前树的某个节点上
询问最后树中一些结点对的距离

Thought

将每个加入的子树看做一个点,考虑维护这些子树的位置关系
边权设为两个子树组合到一起后根节点之间的距离

显然,这同样是一棵树,将其称之为“假树”,类似的,将完整的由多个模板树子树构成的树称之为“真树”

对于“真树”上的两个节点的距离,可以看做两点到“真树”根的距离 $-$ 两点 $LCA$ 到“真树”根的距离 $* 2$

那么算出任意点到“真树”根的距离很简单,也就是该点到其所对应的子树根的距离 $+$ 该子树根到“真树”根的距离

显然,前面的距离可以在模板树上直接维护,后面的距离可以在“假树”上维护

最后的问题就是求 $LCA$ 了,可以先求出两点 $LCA$ 所在子树(也就是属于“假树”上的哪个节点),然后再求是该子树的哪个点

同样,前面求所在子树可以在“假树”上维护,后面求具体点可以在模板树上维护

至于编号对应的是哪个子树的哪个点,可以用前缀和 $+$ lower_bound 找到所在子树,然后用主席树找到子树第 $k$ 大即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read() {
    ll ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
int n, m, q;

int rt[N], pre[N];
ll siz[N];
int dfn[N], low[N], DFN, id[N];
struct Edge {
    int t, n, w;    
};
struct Tree {
    Edge e[N << 1];
    int head[N], tot;
    void addedge(int u, int v, int w) {
        e[++ tot] = {v, head[u], w};
        head[u] = tot;
    }
    int dep[N], siz[N], fa[N][21];
    ll dis[N];

    void dfs(int x, int _f) {
        siz[x] = 1; fa[x][0] = _f;
        dep[x] = dep[_f] + 1;
        for(int i = 1; i <= 20; ++ i)
            fa[x][i] = fa[fa[x][i - 1]][i - 1];
        for(int i = head[x]; i; i = e[i].n) {
            if(e[i].t == _f) continue;
            dis[e[i].t] = dis[x] + e[i].w;
            dfs(e[i].t, x);
            siz[x] += siz[e[i].t];
        }
    }
    void dfsPresident(int x, int _f) {
        dfn[x] = ++ DFN; id[DFN] = x;
        for(int i = head[x]; i; i = e[i].n) {
            if(e[i].t == _f) continue;
            dfsPresident(e[i].t, x);
        }
        low[x] = DFN;
    }
    int lca(int x, int y) {
        if(dep[x] < dep[y]) swap(x, y);
        for(int i = 20; i >= 0; -- i)
            if(dep[fa[x][i]] >= dep[y])
                x = fa[x][i];
        if(x == y) return x;
        for(int i = 20; i >= 0; -- i)
            if(fa[x][i] != fa[y][i]) {
                x = fa[x][i];
                y = fa[y][i];
            }
        return fa[x][0];
    }
    int findSon(int x, int y) {
        for(int i = 20; i >= 0; -- i)
            if(dep[fa[x][i]] > dep[y])
                x = fa[x][i];
        return x;
    }
}t1, t2;
#define L ch[x][0]
#define R ch[x][1]
#define mid ((l + r) >> 1)
struct PresidentTree {
    int rt[N], tot;
    int ch[N * 20][2], siz[N * 20];
    void insert(int &x, int l, int r, int p) {
        ++ tot;
        ch[tot][0] = ch[x][0];
        ch[tot][1] = ch[x][1];
        siz[tot] = siz[x] + 1;
        x = tot;
        if(l == r) return;
        if(p <= mid)
            insert(L, l, mid, p);
        else
            insert(R, mid + 1, r, p);
    }
    void build() {
        for(int i = 1; i <= n; ++ i) {
            rt[i] = rt[i - 1];
            insert(rt[i], 1, n, id[i]);
        }
    }
    int query(int les, int mor, int k , int l, int r) {
        if(l == r) return l;
        if(siz[ch[mor][0]] - siz[ch[les][0]] >= k)
            return query(ch[les][0], ch[mor][0], k, l, mid);
        else
            return query(ch[les][1], ch[mor][1], k - (siz[ch[mor][0]] - siz[ch[les][0]]), mid + 1, r);
    }
}pt;
int main() {
    n = read(); m = read(); q = read();
    for(int i = 1; i < n; ++ i) {
        int u = read(), v = read();
        t1.addedge(u, v, 1);
        t1.addedge(v, u, 1);
    }
    t1.dfs(1, 0);
    t1.dfsPresident(1, 0);
    pt.build();
    rt[0] = 1; siz[0] = n;
    for(int i = 1; i <= m; ++ i) {
        rt[i] = read(); siz[i] = siz[i - 1] + t1.siz[rt[i]];
        ll to = read();
        ll Tnum = lower_bound(siz, siz + i, to) - siz;
        if(Tnum != 0) to -= siz[Tnum - 1];
        pre[i] = pt.query(pt.rt[dfn[rt[Tnum]] - 1], pt.rt[low[rt[Tnum]]], to, 1, n);
        t2.addedge(Tnum, i, (t1.dis[pre[i]] - t1.dis[rt[Tnum]]) + 1);
    }
    t2.dfs(0, 0);
    for(int i = 1; i <= q; ++ i) {
        ll u = read(), v = read();
        ll Tnumu = lower_bound(siz, siz + m + 1, u) - siz;
        ll Tnumv = lower_bound(siz, siz + m + 1, v) - siz;
        if(Tnumu != 0) u -= siz[Tnumu - 1];
        if(Tnumv != 0) v -= siz[Tnumv - 1];
        u = pt.query(pt.rt[dfn[rt[Tnumu]] - 1], pt.rt[low[rt[Tnumu]]], u, 1, n);
        v = pt.query(pt.rt[dfn[rt[Tnumv]] - 1], pt.rt[low[rt[Tnumv]]], v, 1, n);
        ll ans = (t1.dis[u] - t1.dis[rt[Tnumu]] + t2.dis[Tnumu]) + (t1.dis[v] - t1.dis[rt[Tnumv]] + t2.dis[Tnumv]);
        int lca = t2.lca(Tnumu, Tnumv);
        if(Tnumu != lca)
            u = pre[t2.findSon(Tnumu, lca)];
        if(Tnumv != lca)
            v = pre[t2.findSon(Tnumv, lca)];
        int lcap = t1.lca(u, v);
        ans -= (t1.dis[lcap] - t1.dis[rt[lca]] + t2.dis[lca]) * 2;
        printf("%lld\n", ans);
    }
    return 0;
}
Comments

添加新评论