[题解] [JSOI2013] 哈利波特与死亡圣器

题面

题解

转化问题, 即一个点从根节点往下走, 到达任意一个点时, 保证每一个与他直接连通的点都被覆盖了

没有必要向上走, 因为这只会留更多时间来修复

所以我们讨论只下不上的情况

二分一个 mid , 代表当前共有 mid 个人

设 (f[i]) 为到了 (i) 点, 且 (i) 的儿子全部未被覆盖, 需要之前多少次额外的来覆盖

有

[f[i] = max(0, sum f[v] + son[i] - mid) ]

有 mid 个人可以用, 要覆盖 (son[i]) 个儿子, 看还需要多少个额外的来覆盖 (i) 的儿子, 并且要把 (i) 的儿子那棵子树也算上

跟 0 取 (max) 是因为这个点多出来的不能够去补上面的

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 300005; 
using namespace std;

int n, cnt, f[N], sz[N], head[N], ans;
struct edge { int to, nxt; } e[N << 1]; 

template< typename T >
inline T read()
{
    T x = 0, w = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * w; 
}

inline void adde(int u, int v) { e[++cnt] = (edge) { v, head[u] }, head[u] = cnt; }

void dfs(int u, int fa, int mid)
{
    f[u] = -mid, sz[u] = 0;
    for(int v, i = head[u]; i; i = e[i].nxt)
    {
	v = e[i].to; if(v == fa) continue;
	dfs(v, u, mid); sz[u]++;
	f[u] += f[v]; 
    }
    f[u] += sz[u];
    if(f[u] < 0) f[u] = 0; 
}

int main()
{
    n = read <int> ();
    for(int u, v, i = 1; i < n; i++)
    {
	u = read <int> (), v = read <int> ();
	adde(u, v), adde(v, u); 
    }
    int l = 0, r = n;
    while(l <= r)
    {
	int mid = (l + r) >> 1;
	dfs(1, 0, mid);
	if(f[1] == 0) ans = mid, r = mid - 1;
	else l = mid + 1; 
    }
    printf("%d
", ans); 
    return 0; 
}