CF708C Centroids（树形dp，up and down）

2019-06-23
题解
361 次阅读

文章目录

【注意】最后更新于 5年前，文中内容可能已过时，请谨慎使用。

题目链接

CF

洛谷

题意简述

给你一棵 n 个点的树，对每个点，判断能否删去一条边再加上一条边，使得这个点成为树的重心。（树的重心：将其删去后每个联通块大小不超过 n2）

2≤n≤4⋅105​

简要做法

up and down，即用两遍 dfs，第一遍用孩子更新父亲，第二遍用父亲更新孩子，好像也叫做“换根 dp”。

如何修改一条边使一个点成为重心？要把那个点原来最大的子树删掉一条边分成不超过 n2 的两半，再把切下来那个子树接到这个点上。切下来的那个子树只要不超过 n2 即可，所以我们希望切下来一个尽可能大的不超过 n2 的子树，这样剩下来那一半就可以尽量小。

也就是说，我们需要找到以每个点为根的最大子树，以及每个子树（注意是无根树的每个子树）可以切出来的最大的不超过 n2 的子树。求这个可以使用 up and down 这个技巧，详见代码。

求出这个之后，就可以 O(1) 判断每个点是否合法了。

up and down 的过程中有一个小技巧：第二遍 dfs 中用父亲更新孩子时，父亲的 down（父亲的孩子们对父亲的贡献）中要减去当前节点的贡献再更新当前节点的值，所以需要存最大值和次大值，这个可以利用一个小数据结构来简化代码，详见代码中的 struct Node。

参考代码

复制
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 400010;
struct Node
{
    int fi, se;
    void insert(int x) // 向最大值和次大值中插入一个值
    {
        if (x > fi)
        {
            se = fi;
            fi = x;
        }
        else if (x > se) se = x;
    }
    int get(int x) // 得到除了 x 外的最大值
    {
        if (x == fi) return se;
        else return fi;
    }
} dn[N];
int calc(int u);
void dfs1(int u);
void dfs2(int u);
void add(int u, int v);
int head[N], nxt[N << 1], to[N << 1], cnt;
int n, siz[N], fa[N], son[N], up[N];
int main()
{
    int i, u, v, mx, sz;
    scanf("%d", &n);
    for (i = 1; i < n; ++i)
    {
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    dfs1(1);
    dfs2(1);
    for (u = 1; u <= n; ++u)
    {
        v = son[u];
        if (v == fa[u])
        {
            sz = n - siz[u];
            mx = up[u]; // 也可以 max(dn[v].get(calc(u)), up[v])
        }
        else
        {
            sz = siz[v];
            mx = dn[v].fi; // 也可以 calc(v)
        }
        printf("%d ", sz - mx <= n / 2);
    }
    return 0;
}
void dfs1(int u)
{
    int i, v;
    siz[u] = 1;
    for (i = head[u]; i; i = nxt[i])
    {
        v = to[i];
        if (v == fa[u]) continue;
        fa[v] = u;
        dfs1(v);
        siz[u] += siz[v];
        dn[u].insert(calc(v));
    }
}
void dfs2(int u)
{
    int i, v;
    if (n - siz[u] <= n / 2)  up[u] = n - siz[u];
    else up[u] = max(up[fa[u]], dn[fa[u]].get(calc(u)));
    for (i = head[u]; i; i = nxt[i])
    {
        v = to[i];
        if (v == fa[u]) continue;
        dfs2(v);
        if (siz[v] > siz[son[u]]) son[u] = v; // son 是一个节点的最大子树
    }
    if (n - siz[u] > siz[son[u]]) son[u] = fa[u];
}
int calc(int u) // 计算孩子对父亲的贡献
{
    return siz[u] <= n / 2 ? siz[u] : dn[u].fi;
}
void add(int u, int v)
{
    nxt[++cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
}

文章作者 ouuan

上次更新 2020-02-08 (da8aa41) ，更新历史

许可协议 CC BY-SA 4.0

评论正在加载中...如果评论较长时间无法加载，你可以 搜索对应的 issue 或者 新建一个 issue 。