1 条题解

  • 0
    @ 2024-6-28 18:00:47

    设f[u]表示以u为根节点能够得到的最大高度,则取u的f值最大的子节点v,让这个子节点贡献f[v]的高度,其他子节点以及u本身各贡献1的高度即可。

    核心代码
    
    void dfs(int u)
    {
        int sz = g[u].size();
        for (int i = 0; i < sz; i ++)
        {
            int v = g[u][i];
            dfs(v);
            f[u] = f[u] > f[v] ? f[u] : f[v];
        }
        f[u] += sz;
    }
    int main()
    {
        cin >> n;
        for (int i = 2; i <= n; i ++)
        {
            cin >> u;
            g[u].push_back(i);
        }
        dfs(1);
        cout << f[1];
        return 0;
    }
    
    • 1

    信息

    ID
    844
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    (无)
    递交数
    17
    已通过
    12
    上传者