思路与算法

先求每个有向邻接分支的内部广播耗时。已知各分支耗时d，按d降序逐次打电话，总时间max(d_i+i+1)。后序求孩子侧，再前序换根；排序后用前缀max和后缀max排除某个邻居，并将其后的电话次序提前1，得到传向该邻居的父侧耗时。各根答案最后加外部告知的1时间。

正确性说明

两相邻待通知分支若较短者先于较长者，交换后较长者提前、较短者延后，其最大完成时间不会增加，所以降序最优。子树收到消息后的传播彼此独立，由该局部最优归纳。换根完整收集每个邻居方向信息，排除当前方向后准确计算反向分支，故所有起点答案均为最优。

复杂度

各节点邻居排序总O(nlogn)，后序、前后缀和初始化O(n)，时间O(nlogn)，空间O(n)。

易错点

题目最开始把消息告诉首人也耗时1。前后缀排除后，后面的名次要减1；不能简单取最大孩子值。单人答案1，第二行列出全部最优起点，按编号升序。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    vector<int> par(n, -1), ord(1, 0), down(n), up(n), ans(n);
    for (int i = 1, p; i < n; i++) {
        cin >> p;
        --p;
        g[p].push_back(i);
        g[i].push_back(p);
    }
    for (int i = 0; i < n; i++)
        for (int v : g[ord[i]])
            if (v != par[ord[i]]) {
                par[v] = ord[i];
                ord.push_back(v);
            }
    for (int z = n - 1; z >= 0; z--) {
        int u = ord[z];
        vector<int> a;
        for (int v : g[u])
            if (v != par[u])
                a.push_back(down[v]);
        sort(a.rbegin(), a.rend());
        for (int i = 0; i < (int)a.size(); i++)
            down[u] = max(down[u], a[i] + i + 1);
    }
    for (int u : ord) {
        vector<pair<int, int>> a;
        for (int v : g[u])
            a.push_back({v == par[u] ? up[u] : down[v], v});
        sort(a.rbegin(), a.rend());
        int d = a.size();
        vector<int> pre(d + 1), suf(d + 1);
        for (int i = 0; i < d; i++)
            pre[i + 1] = max(pre[i], a[i].first + i + 1);
        for (int i = d - 1; i >= 0; i--)
            suf[i] = max(suf[i + 1], a[i].first + i);
        ans[u] = 1 + pre[d];
        for (int i = 0; i < d; i++)
            if (a[i].second != par[u])
                up[a[i].second] = max(pre[i], suf[i + 1]);
    }
    int best = *min_element(ans.begin(), ans.end());
    cout << best << '\n';
    for (int i = 0; i < n; i++)
        if (ans[i] == best)
            cout << i + 1 << ' ';
    cout << '\n';
}