【题解】LOJ 2206 「HNOI2014」世界树

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

Problem

给定一棵 $n$ 个节点的树

每次询问给出一些关键点,树上的点属于距离最近的关键点管辖
计算出每个关键点各管辖多少个点

Thought

发现关键点总数和 $n$ 同阶
考虑虚树

建出虚树后,在虚数上做 DP ,分别计算出每个点距离最近的关键点,并且统计答案

注意到有些点并不在虚树中,但是显然他们的贡献也是要计算的
假设原树中某点有一个子树,而虚树中这个子树没有出现,那么整个子树都属于管辖该点的关键点
同样,对于虚树上相邻的两个点对应的原树上的一段,我们需要找出两个管辖点的中点计算答案,这里利用倍增即可完成

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 300010;
struct Edge {
    int t, n;
}e[N << 1], E[N];
int head[N], headE[N];
int tot, totE;

int dfn[N], DFN, dep[N], siz[N];
int fa[N][21];

int h[N], key[N], sta[N], top;

int ans[N];
int master[N];
int rem[N];

int n, m;

void addedge(int u, int v) {
    e[++ tot] = {v, head[u]};
    head[u] = tot;
}
void addEdge(int u, int v) {
    E[++ totE] = {v, headE[u]};
    headE[u] = totE;
}

void dfs(int x, int _f) {
    dep[x] = dep[_f] + 1; dfn[x] = ++ DFN; siz[x] = 1;
    fa[x][0] = _f;
    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;
        dfs(e[i].t, x);
        siz[x] += siz[e[i].t];
    }
}
int lca(int a, int b) {
    if(dep[a] < dep[b]) swap(a, b);
    for(int i = 20; i >= 0; -- i)
        if(dep[fa[a][i]] >= dep[b])
            a = fa[a][i];
    if(a == b) return a;
    for(int i = 20; i >= 0; -- i)
        if(fa[a][i] != fa[b][i]) {
            a = fa[a][i];
            b = fa[b][i];
        }
    return fa[a][0];
}
int dis(int a, int b) {
    int c = lca(a, b);
    return dep[a] + dep[b] - dep[c] * 2;
}
int getFa(int x, int _f) {
    for(int i = 20; i >= 0; -- i)
        if(_f & (1 << i))
            x = fa[x][i];
    return x;
}

bool cmp(int a, int b) {
    return dfn[a] < dfn[b];
}

void update(int x, int y) {
    if(!master[x])
        master[x] = master[y];
    else {
        int disx = dis(master[x], x);
        int disy = dis(master[y], x);
        if(disy < disx || (disx == disy && master[y] < master[x]))
            master[x] = master[y];
    }
}
void DP1(int x) {
    rem[x] = siz[x];
    if(key[x])
        master[x] = x;
    else
        master[x] = 0;
    for(int i = headE[x]; i; i = E[i].n) {
        DP1(E[i].t);
        update(x, E[i].t);
    }
}
void solve(int a, int b) {
    int x = a, mid = a;
    for(int i = 20; i >= 0; -- i)
        if(dep[fa[x][i]] > dep[b])
            x = fa[x][i];
    rem[b] -= siz[x];
    if(master[a] == master[b])
        ans[key[master[a]]] += siz[x] - siz[a];
    else {
        for(int i = 20; i >= 0; -- i) {
            int nxt = fa[mid][i];
            if(dep[nxt] <= dep[b]) continue;
            int d1 = dis(master[a], nxt), d2 = dis(master[b], nxt);
            if(d1 < d2 || (d1 == d2 && master[a] < master[b]))
                mid = nxt;
        }
        ans[key[master[a]]] += siz[mid] - siz[a];
        ans[key[master[b]]] += siz[x] - siz[mid];
    }
}
void DP2(int x,int _f) {
    if(_f) {
        update(x, _f);
        solve(x, _f);
    }
    for(int i = headE[x]; i; i = E[i].n)
        DP2(E[i].t, x);
    ans[key[master[x]]] += rem[x];
    rem[x] = 0;
}
int main() {
    n = read();
    for(int i = 1; i < n; ++ i) {
        int u = read(), v = read();
        addedge(u, v);
        addedge(v, u);
    }
    dfs(1, 0);

    int q = read();
    while(q --) {
        m = read();
        for(int i = 1; i <= m; ++ i) {
            h[i] = read();
            key[h[i]] = i;
        }
        sort(h + 1, h + m + 1, cmp);
        
        totE = 0;
        headE[1] = 0;
        sta[top = 1] = 1;
        for(int i = 1; i <= m; ++ i) {
            if(h[i] == 1) continue;
            int c = lca(h[i], sta[top]);
            if(c != sta[top]) {
                while(top >= 2 && dep[c] <= dep[sta[top - 1]]) {
                    addEdge(sta[top - 1], sta[top]);
                    sta[top --] = 0;
                }
                if(c != sta[top]) {
                    headE[c] = 0;
                    addEdge(c, sta[top]);
                    sta[top] = c;
                }
            }
            headE[h[i]] = 0;
            sta[++ top] = h[i];
        }
        for(int i = 1; i < top; ++ i)
            addEdge(sta[i], sta[i + 1]);
        DP1(1); DP2(1, 0);
        for(int i = 1; i <= m; ++ i) {
            printf("%d ", ans[i]);
            ans[i] = 0;
        }
        puts("");
        for(int i = 1; i <= m; ++ i)
            key[h[i]] = 0;
    }
    return 0;
}
Comments

添加新评论