『Noi2016十连测第二场 - 深邃』

pdf版题面 在线提交（需要权限）

题目

问题描述

当我们伟大的领袖 V 还小的时候，他的目光就十分深邃，显示出他过人的天赋。这一天，他将目光投向了贤者之森里的一棵树。

这是一棵有$n$个节点$n-1$条边的树，其中有$k$个节点长有果实， V 想删去一些边，使得树分为几个连通块，满足每个连通块都包含至少一个果实，并且最大的连通块最小。 V 请你求出答案，thank you sir!

输入格式

第一行两个正整数，分别表示$n$和$k$。

接下来$n-1$行每行两个数表示一条边，节点从$1$开始编号。

接下来一行$k$个整数，表示长有果实的节点，保证不会重复。

输出格式

一行一个正整数表示答案。

样例输入

5 2
1 2
2 3
3 4
4 5
1 5

样例输出

3

数据范围与约定

对于$20\%$的数据$n \leq 20$

对于另外$20\%$的数据$n \leq 2000$

对于另外$20\%$的数据$k = 2$

对于另外$20\%$的数据$k = 3$

对于$100\%$的数据$k \leq n \leq 200000$

题解

（稍后再补）

代码

#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
#define MAXN 400010
int readint()
{
    int x = 0, c;
    while (!isdigit(c = getchar()));
    do
        x = x * 10 + c -'0';
    while (isdigit(c = getchar()));
    return x;
}
int n, k;
bool fruit[MAXN];
vector<int> edge[MAXN];
bool vised[MAXN];
int fa[MAXN];
void dfs(int now)
{
    vised[now] = 1;
    int sz = (int)edge[now].size();
    for (int i = 0; i < sz; i++)
    {
        int v = edge[now][i];
        if (!vised[v])
        {
            fa[v] = now;
            dfs(v);
        }
    }
}
int s[MAXN];
void count(int now, int k)
{
    int sz = (int)edge[now].size();
    for (int i = 0; i < sz; i++)
    {
        int v = edge[now][i];
        if (fa[v] == now)
            count(v, k);
    }
    if (fruit[now])
    {
        s[now] = 1;
        for (int i = 0; i < sz; i++)
        {
            int v = edge[now][i];
            if (fa[v] == now && s[v] < 0)
                s[now] += -s[v];
             
        }
    }
    else
    {
        int ms = n + 1, delta = 1;
        for (int i = 0; i < sz; i++)
        {
            int v = edge[now][i];
            if (fa[v] == now && s[v] > 0 && s[v] < ms)
                ms = s[v];
            if (fa[v] == now && s[v] < 0)
                delta += -s[v];
        }
        if (ms + delta <= k)
            s[now] = ms + delta;
        else
            s[now] = -delta;
    }
}
bool check(int mid)
{
    memset(s, 0, sizeof(s));
    count(1, mid);
    for (int i = 1; i <= n; i++)
        if (abs(s[i]) > mid)
            return false;
    if (s[1] < 0)
        return false; 
    return true;
}
int main()
{
	freopen("deep.in", "r", stdin);
	freopen("deep.out", "w", stdout);
    n = readint();
    k = readint();
    for (int i = 1; i < n; i++)
    {
        int u = readint();
        int v = readint();
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for (int i = 0; i < k; i++)
        fruit[readint()] = 1;
    dfs(1);
    int l = 1, r = n;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    printf("%d\n", l);
    return 0;
}