Description

2020 年, 人类在火星上建立了一个庞大的基地群, 总共有 \(n\) 个基地. 起初为了节约材料, 人类只修建了 \(n - 1\) 条道路来连接这些基地, 并且每两个基地都能够通过道路到达, 所以所有的基地形成了一个巨大的树状结构. 如果基地 \(A\) 到基地 \(B\) 至少要经过 \(d\) 条道路的话, 我们称基地 \(A\) 到基地 \(B\) 的距离为 \(d\). 由于火星上非常干燥, 经常引发 火灾, 人类决定在火星上修建若干个消防局. 消防局只能修建在基地里, 每个消防局有能力 扑灭与它距离不超过 \(2\) 的基地的火灾. 你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时, 消防队有能力及时扑灭火灾.

Input

输入文件的第一行为 \(n\), 表示火星上基地的数目. 接下来的 \(n - 1\) 行每行有一个正整数, 其中文件第 \(i\) 行的正整数为 \(a_i\), 表示从编号为 \(i\) 的基地到编号为 \(a_i\) 的基地之间有一条道路.

(BZOJ 上的题干似乎出了点问题)

Output

输出文件仅有一个正整数, 表示至少要设立多少个消防局才有能力及时扑灭任何基地发生的 火灾.

Sample Input

6
1
2
3
4
5

Sample Output

2

Explanation

可以考虑这样的情况: 首先是树形动规这个没法说

然后发现两个消防站离得越远越好 (当然能够覆盖), 所以此题变成了贪心

应该距离为 5 最佳

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 2010, maxm = 10010;

class TreeDP
{
public:
    struct edge
    {
        int u, v;
        edge *next;
    };
    int n, ecnt, dp[maxn];
    edge *edges[maxn], epool[maxm];
    void add_edge(int u, int v)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v;
        p->next = edges[u]; edges[u] = p;
        q->u = v; q->v = u;
        q->next = edges[v]; edges[v] = q;
        return ;
    }
    bool vis[maxn];
    int res;
    void dfs(int p)
    {
        vis[p] = true;
        int mn = maxn, mx = -maxn;
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (!vis[ep->v]) {
                dfs(ep->v);
                mn = min(dp[ep->v], mn);
                mx = max(dp[ep->v], mx);
            }
        // The maximum depth of unresolved nodes is dp[p].
        if (mn + mx <= 3)
            dp[p] = mn + 1;
        else
            dp[p] = mx + 1;
        if (mn == maxn)
            dp[p] = 3;
        if (dp[p] == 5)
            res++, dp[p] = 0;
        return ;
    }
    int eval(void)
    {
        res = 0;
        dfs(1);
        if (dp[1] > 2)
            res++;
        return res;
    }
} graph;

int n;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    graph.n = n;
    for (int i = 2, x; i <= n; i++) {
        scanf("%d", &x);
        graph.add_edge(i, x);
    }
    int res = graph.eval();
    printf("%d\n", res);
    return 0;
}