题解 P5666 【树的重心【民间数据】】

· · 题解

本做法洛谷上可以通过, 发篇题解攒攒人品.

标签:主席树, dfs序, 树状数组.

容易想到对每个点分别求贡献(即求每个点割去那些边会成为重心), 我们选择任意一个点(就是 1号节点辣!)将其作为根节点.

模仿题目中的描述, 定义 u 的 分裂子树 表示在树中删去 u 及与它关联的边后, 分裂出的子树, 那么一条边 e 对一个点 u 有贡献, 当且仅当割去 e 后, 考虑 u 所在的一部分(记这部分的大小为 tmp, 记另一部分为割去的部分), u 最大的分裂子树 的大小不大于 \lfloor \frac{tmp}2\rfloor.

Part 1

首先我们先考虑根结点的贡献, 我们先求出根节点的每一棵儿子的子树的大小 size, 取 size 最大的儿子记为 mx.

显然如果我们割掉的边不在 mx 的子树内, u 最大的分裂子树 的大小不会改变, 那么这条边有贡献需要满足size_{mx}\leqslant \lfloor\frac{n-t}{2}\rfloor, 其中 t 表示割去的部分 的大小, 稍加变形后得到 t\leqslant n-2\times size_{mx}.

考虑割掉的边在 mx 的子树内, u 的最大 分裂子树 可能会变成原来次大的(记为 mx' ), 那么我们需要满足 size_{mx}-t\leqslant \lfloor\frac{n-t}{2}\rfloor, size_{mx'}\leqslant \lfloor\frac{n-t}{2}\rfloor, 稍加变形后得到 2\times size_{mx}-n\leqslant t\leqslant n-2\times size_{mx'}.

所以我们需要知道 t 取每个值的方案数, 显然 t 的一个取值对应了一个节点子树的大小, 我们对每个根的儿子求出其子树内 t 的取值情况, 在分别求出合法的 t 的方案就好了.

复杂度 \mathcal O(n), 事实上枚举每个点做根求一遍答案可以做到 \mathcal O(n^2).

Part 2

接下来考虑其他点的贡献, 发现其他点与根节点唯一的区别就是具有 外子树 (指断掉与父亲节点的连边的那棵子树), 那么该如何维护外子树的 t 的取值呢?

发现我们可以很容易地在 \mathcal O(n\log n) 的时间内通过 线段树合并, 主席树+dfs序 等方法来维护 内子树 (与外子树相对)的 t 的取值, 这里不赘述, 那么是否可以维护整棵树对于某个点的 t 的取值呢? 这样减去内子树的部分, 就可以得到外子树的 t 的取值了.

事实上这是可以维护的, 首先整棵树对于根结点的 t 取值就是处根节点外所有点的子树大小. 考虑我们已知整棵树对点 u 的情况, 如何求 u 的一个儿子 v 的情况呢? 发现 u, v 断去某条边的 t 不同当且仅当这条边是 (u,v), 所以 v 的 t 的取值比 u 多了一个 n-sz_v, 少了一个 sz_v. 于是我们可以边dfs边维护整棵树对于某个点的 t 的取值了, 这里要用到树状数组/线段树, 复杂度是 \mathcal O(n\log n) 的.

时间复杂度 \mathcal O(n\log n) , 空间复杂度 \mathcal O(n\log n) .

代码不敢贴, 怕被hack

upd, 把代码补上, 不然可能看不太懂哈.

#include <bits/stdc++.h>
using namespace std;
int read();

int n;

int hd[300005], nx[600005], to[600005], cnt;
void add(int f, int t) { nx[++cnt] = hd[f], hd[f] = cnt, to[cnt] = t; }

struct Bit {
    int ts[300005];
    void add(int p, int v) {
        for (; p <= n; p += p & (-p)) ts[p] += v;
    }
    int qry(int l, int r) {
        if (l > r) return 0;
        l--;
        int rt = 0;
        while (l != r) {
            if (l > r) rt -= ts[l], l -= l & (-l);
            if (r > l) rt += ts[r], r -= r & (-r);
        }
        return rt;
    }
} bit;

int sz[300005], mx[300005][2];

struct P {
    int u, l, r;
} w[600005];

int root[300005];
struct Pseg {
    int idcnt;
    int ls[10000007], rs[10000007], ts[10000007];
    void add(int &x, int k, int l, int r, int p) {
        ts[x = ++idcnt] = ts[k] + 1, ls[x] = ls[k], rs[x] = rs[k];
        if (l == r) return;
        int mid = l + r >> 1;
        (p <= mid) ? add(ls[x], ls[k], l, mid, p)
            : add(rs[x], rs[k], mid + 1, r, p);
    }
    int qry(int k1, int k2, int l, int r, int st, int en) {
        if (st > r || en < l) return 0;
        if (st <= l && en >= r) return ts[k2] - ts[k1];
        int mid = l + r >> 1;
        return qry(ls[k1], ls[k2], l, mid, st, en) + qry(rs[k1], rs[k2], mid + 1, r, st, en);
    }
} seg;

long long res;

int l[300005], r[300005], L[300005], R[300005];
int pre[300005], pst[300005], frt[300005], dfn;
int fa[300005];
void dfs1(int u) {
    sz[u] = 1, root[pre[u] = ++dfn] = 0, frt[dfn] = u, mx[u][0] = mx[u][1] = 0;
    int tmx = 0, tci = 0;
    for (int i = hd[u], v; i; i = nx[i]) {
        if ((v = to[i]) == fa[u]) continue;
        fa[v] = u, dfs1(v), sz[u] += sz[v];
        if (sz[mx[u][1]] < sz[v]) mx[u][1] = v;
        if (sz[mx[u][0]] < sz[mx[u][1]]) swap(mx[u][0], mx[u][1]);
    }
    if (fa[u]) bit.add(sz[u], 1);
    tmx = sz[mx[u][0]], tci = sz[mx[u][1]];
    if (sz[mx[u][1]] < n - sz[u]) {
        mx[u][1] = fa[u], tci = n - sz[u];
        if (sz[mx[u][0]] < n - sz[u]) 
            swap(mx[u][0], mx[u][1]), swap(tmx, tci);
    }
    L[u] = 1, R[u] = n - tmx * 2; 
    l[u] = max(1, 2 * tmx - n), r[u] = n - 2 * tci;
    pst[u] = dfn;
}

void dfs2(int u) {
    res += 1ll * u * ((mx[u][0] == fa[u]) ? 
                      bit.qry(l[u], r[u]) : bit.qry(L[u], R[u]));
    for (int i = hd[u]; i; i = nx[i])
        if (to[i] != fa[u]) {
            bit.add(sz[to[i]], -1), bit.add(n - sz[to[i]], 1);
            dfs2(to[i]);
            bit.add(sz[to[i]], 1), bit.add(n - sz[to[i]], -1);
        }
}

int main() {
    int T = read();
    while (T--) {
        n = read(), cnt = 0, res = 0, dfn = 0, seg.idcnt = 0;
        for (int i = 1; i <= n; ++i) hd[i] = 0;
        for (int i = 1, u, v; i < n; ++i)
            u = read(), v = read(), add(u, v), add(v, u);
        for (int i = 1; i <= n; ++i) bit.ts[i] = 0;
        dfs1(1), dfs2(1);
        for (int i = 1; i <= n; ++i)
            seg.add(root[i], root[i - 1], 1, n, sz[frt[i]]);
        for (int u = 1; u <= n; ++u) {
            if (mx[u][0] != fa[u]) {
                for (int i = hd[u], v; i; i = nx[i]) {
                    if ((v = to[i]) == mx[u][0]) {
                        res -= 1ll * u * 
                            seg.qry(root[pre[v] - 1], root[pst[v]], 1, n, L[u], R[u]);
                        res += 1ll * u * 
                            seg.qry(root[pre[v] - 1], root[pst[v]], 1, n, l[u], r[u]);
                    }
                }
            } else {
                res -= 1ll * u * 
                    seg.qry(root[pre[u]], root[pst[u]], 1, n, l[u], r[u]);
                res += 1ll * u * 
                    seg.qry(root[pre[u]], root[pst[u]], 1, n, L[u], R[u]);
            }           
        }
        printf("%lld\n", res);
    }
    return 0;
}

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c)) f = (c == '-') ? -1 : f, c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    return x * f;
}