CF196 D2 D

Book of Evil，有一颗树，n个节点，有m个节点被标记，问n个节点中，有多少个节点，这些节点与这m个节点的最远的距离小于等于d。

用down[i], up[i]分别标记只考虑以i为root的子树的情况与这颗补集并上节点i的情况，两遍dfs，第一遍dfs求出down数组，第二遍求up数组，求up时，需要考虑当前节点i的父亲节点的up值以及节点i的兄弟节点的down值，然后取最大值。在求兄弟们的最大值时，由于所有的兄弟都会有这样的操作，因此可以先求出最大和次大，如果当前节点i的down值不是最大的，那么最大的一定在兄弟中，否则次大的一定是兄弟中最大的。

PS: 还个算法，可以先求出树中离得最远的两个带标记的节点，枚举树中的节点，若节点与这两个节点的距离小于等于d，则统计。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

const int MAXN = ;

const int INF = 1e9;

int down[MAXN], up[MAXN];

int max1[MAXN], max2[MAXN];

bool p[MAXN];

vector<vector<int> > tree;

void dfs1(int u, int f) {

    down[u] = p[u] ?  : -INF;

    max1[u] = max2[u] = -INF;

    for (int i = ; i < tree[u].size(); i++) {

        int v = tree[u][i];

        if (v != f) {

            dfs1(v, u);

            down[u] = max(down[u], down[v] + );

            if (down[v] > max1[u]) {

                max2[u] = max1[u];

                max1[u] = down[v];

            } else if (down[v] > max2[u]) {

                max2[u] = down[v];

            }

        }

    }

}

void dfs2(int u, int f) {

    up[u] = p[u] ?  : -INF;

    if (f != -) {

        up[u] = max(up[u], up[f] + );

        int slide;

        if (down[u] < max1[f]) {

            slide = max1[f] + ;

        } else {

            slide = max2[f] + ;

        }

        up[u] = max(up[u], slide);

    }

    for (int i = ; i < tree[u].size(); i++) {

        int v = tree[u][i];

        if (v != f) {

            dfs2(v, u);

        }

    }

}

int main() {

    int n, m, d;

    scanf("%d%d%d", &n, &m, &d);

    memset(p, false, sizeof(p));

    for (int i = ; i < m; i++) {

        int t;

        scanf("%d", &t);

        p[t] = true;

    }

    tree.resize(n + );

    for (int i = ; i < n; i++) {

        int a, b;

        scanf("%d%d", &a, &b);

        tree[a].push_back(b);

        tree[b].push_back(a);

    }

    dfs1(, -);

    dfs2(, -);

    int ans = ;

    for (int i = ; i <= n; i++) {

        if (max(down[i], up[i]) <= d) {

            ans++;

        }

    }

    printf("%d\n", ans);

}

巴特西

CF196 D2 D

最新文章

热门文章