CF337D Book of Evil

传送门

Solution

设 $a_u$ 表示以 $u$ 为根的子树中，离 $u$ 最远的重要结点，$b_u$ 表示以 $u$ 为根的子树中，离 $u$ 次远的重要结点，$c_u$ 表示以 $u$ 为根的子树外离 $u$ 最远的结点。

第一遍 dfs，从下往上 dp 出 $a_u$ 和 $b_u$。第二遍 dfs，从上往下求出 $c_u$。设 $v$ 为 $u$ 的儿子，通过 $a_u$ 是否等于 $a_v+1$ 可判断 $a_u$ 是否从 $a_v$ 中转移得到。若是，则 $c_v=\max\{c_u,b_u\}+1$。否则 $c_v=\max\{c_u,a_u\}+1$

$u$ 满足题意，当且仅当 $\max\{c_u,a_u\}\le d$。

时间复杂度 $O(n)$。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, m, d, a[N], b[N], fa[N], mp[N], ans, c[N];
vector<int> g[N];

void change(int u, int c)
{
    if (a[u] <= c) {
        b[u] = a[u];
        a[u] = c;
    } else if (b[u] <= c)
        b[u] = c;
}

void dfs1(int u, int pre)
{
    fa[u] = pre;
    for (int v : g[u]) {
        if (v == pre) continue;
        dfs1(v, u);
        if (a[v])
            change(u, a[v] + 1);
        else if (mp[v])
            change(u, 1);
    }
}

void dfs2(int u)
{
    for (int v : g[u]) {
        if (v == fa[u]) continue;
        if (c[u])
            c[v] = c[u] + 1;
        if (mp[u]) 
            c[v] = max(c[v], 1);
        if (a[u] && (a[u] != a[v] + 1 || (!a[v] && !mp[v])))
            c[v] = max(c[v], a[u] + 1);
        else if (a[u] == a[v] + 1 && b[u])
            c[v] = max(c[v], b[u] + 1);
        dfs2(v);
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &d);
    for (int i = 1; i <= m; i++) {
        int u;
        scanf("%d", &u);
        mp[u] = 1;
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1, 0); dfs2(1);
    for (int i = 1; i <= n; i++)
        if (max(c[i], a[i]) <= d)
            ans++;
    printf("%d", ans);
    return 0;
}