WA on #3 求调!
查看原帖
WA on #3 求调!
244309
yuhaocheng楼主2022/7/22 21:44
#include <bits/stdc++.h>
using namespace std;

#define MAXN 1005

int n, m, d;
int a[MAXN];
vector<int> g[MAXN];
int dp1[MAXN]; // 子树内
int mx[MAXN][2];
int mxp[MAXN]; // dp1 最大值出现的位置(子树)
int dp2[MAXN]; // 子树外

void dfs1(int x, int fa) {
    if (a[x]) {
        mx[x][0] = -1;
        mx[x][1] = -1;
    } else if (g[x].size() == 1 && g[x][0] == fa) {
        mx[x][0] = -0x0f0f0f0f;
        mx[x][1] = -0x0f0f0f0f;
    }
    for (int c : g[x]) {
        if (c == fa) {
            continue;
        }
        dfs1(c, x);
        if (dp1[c] > mx[x][0]) {
            mxp[x] = c;
            mx[x][1] = mx[x][0];
            mx[x][0] = dp1[c];
        } else if (dp1[c] > mx[x][1]) {
            mx[x][1] = dp1[c];
        }
    }
    dp1[x] = mx[x][0] + 1;
}

void dfs2(int x, int fa) {
    if (a[x]) {
        dp2[x] = 0;
    }
    if (fa != -1) {
        dp2[x] = dp2[fa] + 1;
        if (mx[fa][0] && mxp[fa] != x) {
            dp2[x] = max(dp2[x], mx[fa][0] + 2);
        } else if (mx[fa][1]) {
            dp2[x] = max(dp2[x], mx[fa][1] + 2);
        }
    } else {
        dp2[x] = -0x0f0f0f0f;
    }
    for (int c : g[x]) {
        if (c == fa) {
            continue;
        }
        dfs2(c, x);
    }
}

int main() {
    memset(dp1, -0x0f, sizeof(dp1));
    memset(dp2, -0x0f, sizeof(dp2));
    cin >> n >> m >> d;
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        a[x] = 1;
    }
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1, -1);
    dfs2(1, -1);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (max(dp1[i], dp2[i]) <= d) {
            ans++;
        }
    }
    cout << ans << endl;
}
2022/7/22 21:44
加载中...