bzoj 5174: [Jsoi2013]哈利波特与死亡圣器

.

%%%GXZLegend
代码：

#include<bits/stdc++.h>
using namespace std;

int n, num = 0, fst[300010], f[300010];
struct edge
{
    int x, y, n;
}e[600010];

void ins(int x, int y)
{
    e[++num] = {x, y, fst[x]};
    fst[x] = num;
}
void dfs(int x, int fa, int md)
{
    // printf("%d\n", x);
    f[x] = -md;
    for (int i = fst[x]; i; i = e[i].n)
    {
        int y = e[i].y;
        if (y == fa)
            continue;
        dfs(y, x, md);
        f[x] += f[y] + 1;
    }
    if (f[x] < 0)
        f[x] = 0;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        ins(x, y);
        ins(y, x);
    }
    int l = 0, len = n + 1;
    while (len)
    {
        int md = l + (len >> 1);
        dfs(1, 0, md); /*
        printf("%d\n", md);
        for (int i = 1; i <= n; i++)
            printf("%d ", f[i]);
        puts("");*/
        if (f[1])
        {
            l = md + 1;
            len = len - (len >> 1) - 1;
        }
        else
            len >>= 1;
    }
    printf("%d\n", l);
}