AGC009B 题解

注意到如果把每一对胜者败者连边，可以得到一颗树：

（例子）

但是因为胜者每次只能和一个败者打，所以要用类似多叉转二叉的方法，让有不止一个孩子的节点变成有一个孩子和一个虚点。

如图，原来 \(1\) 有三个儿子 \(2,3,4\)，通过转换，变成了上图。

上图可以直接变成对战图（\(x2\to x1\to 1）\)：

（原树不可以换根，否则构造出的对战图是错的！）

对战图深度即为树的深度。

所以这变成了求出转化后树深度最小值。

根据贪心，一定是越深的子树越靠近父节点（经过的虚点最少）。

所以应该是：

于是设 \(f_i\) 为以 \(i\) 为根的子树深度最小值。

根据上面结论，直接 dp 即可。

也就是求出儿子排列 \(p\) 使得 \(\max_{i=1}^{sz(sons)}f_{p_i}+i\) 最小。

显然 \(p\) 按照 \(f\) 为关键字排序就可以了。

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

const int N = 1e5 + 5;

vector<int> e[N];
int n, f[N];

void dfs1(int x, int fa)
{
    vector<int> v;
    for(int i : e[x])
    {
        dfs1(i, x);
        v.push_back(f[i]);
    }
    sort(v.begin(), v.end(), greater<>());
    for(int i = 0; i < v.size(); i ++)
        f[x] = max(f[x], v[i] + i + 1);
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for(int i = 2; i <= n; i ++)
    {
        int x; cin >> x;
        e[x].push_back(i);
    }
    dfs1(1, 0);
    cout << f[1];

    return 0;
}