ACM模版

描述

题解

先吐槽一下，我只想说，搞 ACM 的人语文表达能力真的很有限，说得云里雾里的……一开始有思路，瞄了一眼讨论区，思路彻底被搞蒙了，这表达能力堪忧啊~~~抑或是我的语文理解能力低下？

这个题能够用最小割解，十分不错，反正我不会，也就点点赞~~~

我用的是树归，因为很明显是 dp，又是树，所以就是树归喽~~~建图，不多说，保存一下每个点的度，根据度，判断 −1 ，然后随便找一个度为 1 的点，作为根，进行树归。

这里，我们需要从叶子开始往根查找，也就是说需要从底往上进行规划，此时，我们需要考虑的是每一个点作为子树的根时，它的儿子的情况。而他的儿子的情况大致分为三种，
0：他的这个儿子不能通往叶子，并且没有犯人可以到达他的这个儿子，也就是说从这棵子树的根和这个儿子之间的一切联系都是无所谓的了；
1：他的这个儿子可以通往叶子，也就是说从这棵子树的根可以到达叶子，这种情况我们可以肯定的是，这些路径中肯定不会有犯人（因为从儿子能通往的叶子可能不唯一），因为如果有的话，我们肯定会在更深一层的递归中堵住这条路；
2：他的这个儿子不能通往叶子，但是有犯人可以到达这个儿子，此时，我们就需要格外关注这种情况了。

通过 state[] 对上述三种情况的儿子进行计数后，我们可以结合起来分析根了。
第一种，如果根就是犯人的位置，那么很不幸，我们需要把所有的第 1 类儿子进行封杀，也就是说需要 ans += state[1]，此时，不管其他儿子啥情况，这个子树的根都是第 2 类情况；
第二种，既存在第 1 类儿子，又存在第 2 类儿子，那么，第 2 类儿子中的犯人可以通过根节点到达能够通往叶子结点的儿子那里，所以此时最佳操作不是封杀所有第 2 类儿子，而是直接封杀根，那么需要 ans++，此时根变为第 0 类情况；
第三种，如果有第 1 类或者第 2 类儿子，那么根也是同样的情况，如果只有第 0 类儿子，那么根也是同样的情况，注意判断的优先级，前两类可以不分前后，但是第 0 类的要最后判断，自己想想为什么，很容易想的，如果三类儿子都没有，那么说明他就是叶子，此时，我们应该注意到，所有叶子（出口）结点或者所有结点的状态都应该初始化为可以通往出口了~~~

这个题思路不难，但是需要理清晰，不然很容易弄错情况的~~~一开始我就是被打乱了思路，苦恼(￣o￣) . z Z

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 1e5 + 5;

int n, m;
int ans;
int cnt = 0;
int dg[MAXN];           // 度
int flag[MAXN];
int prisoner[MAXN];     // 犯人
vector<int> vi[MAXN];

void dfs(int x, int pre)
{
    int state[3];       // 三种状态
    memset(state, 0, sizeof(state));
    for (int i = 0; i < vi[x].size(); i++)
    {
        if (vi[x][i] != pre)
        {
            dfs(vi[x][i], x);
            state[flag[vi[x][i]]]++;
        }
    }

    if (prisoner[x])    // x 点有逃犯
    {
        ans += state[1];// 加上所有能到达的叶子（出口）的儿子结点数
        flag[x] = 2;    // x 变为不能通向叶子（出口）的儿子结点
    }
    else if (state[1] && state[2])  // 有叶子（出口）可以通到 x 并且有其他犯人可以到达 x
    {
        ans++;          // x 处放置警察
        flag[x] = 0;    // 不能到达 x
    }
    else if (state[1])  // x 是否可以通往叶子（出口）
    {
        flag[x] = 1;    // x 变为可以通往出口
    }
    else if (state[2])  // 是有犯人可以到达 x
    {
        flag[x] = 2;    // x 变为有犯人到达
    }
    else if (state[0])  // 不能到达叶子（出口）
    {
        flag[x] = 0;    // x 不能通往叶子（出口）
    }
}

// 初始化所有结点都可以通往出口
void init()
{
    for (int i = 0; i < MAXN; i++)
    {
        flag[i] = 1;
    }
}

int main()
{
    init();

    cin >> n >> m;
    n++;

    int x, y;
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d", &x, &y);
        vi[x].push_back(y);
        vi[y].push_back(x);
        dg[x]++;
        dg[y]++;
    }

    for (int i = 1; i <= m; i++)
    {
        scanf("%d", &x);
        if (dg[x] == 1)
        {
            printf("-1\n");
            return 0;
        }
        prisoner[x] = 1;
    }

    for (int i = 0; i < n; i++)
    {
        if (dg[i] == 1)
        {
            dfs(i, 0);
            if (flag[i] == 2)   // 有犯人能到达根节点
            {
                ans++;
            }
            break;
        }
    }
    printf("%d\n", ans);

    return 0;
}