看了下别人讨论的题解才想到的，不过方法和他的不同，感觉它的是错的。（感觉、感觉）
首先N只有1000， 如果能做到暴力枚举每一个节点，然后O（N）算出其贡献，那么也在允许的时间内。
假设我们现在对1这个节点进行计数，设dp[i]表示入侵i号节点和其所有子树所需要的最小时间。
那么、假设1号有k个儿子，dp[son1] 、 dp[son2]、 dp[sonk]都算出来了，那么dp[1] = max(dp[son])对吧。
但是入侵这些儿子都有一定的规矩，就是每一秒只能入侵一个，那么总是有一些儿子是最后才入侵的，就是要隔k秒后（最坏情况）才入侵这个儿子，
所以把所有儿子的权值排序，要使得max值最小，那么dp[son]值最小的，我们最后才入侵
dp[son1] += k
dp[son2] += k - 1
dp[son3] += k - 2
......
这样是最优的。
然后这一个过程时间是O(nlogn)
也能接受。
注意的是输出的时候id要按小到大输出，不然wa9
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> const int maxn = 1e3 + 20; struct Edge { int u, v, tonext; }e[maxn * 2]; int first[maxn], num; void addEdge(int u, int v) { ++num; e[num].u = u, e[num].v = v, e[num].tonext = first[u]; first[u] = num; } int dp[maxn]; vector<int>vc[maxn]; int dfs(int cur, int fa) { int son = 0; vc[cur].clear(); for (int i = first[cur]; i; i = e[i].tonext) { int v = e[i].v; if (fa == v) continue; son++; vc[cur].push_back(dfs(v, cur)); } if (vc[cur].size() == 0) return 0; sort(vc[cur].begin(), vc[cur].end()); for (int i = 0; i < vc[cur].size(); ++i) { vc[cur][i] += son; son--; } sort(vc[cur].begin(), vc[cur].end()); return vc[cur].back(); } struct Node { int val, id; Node(int _val, int _id) { val = _val, id = _id; } bool operator < (const struct Node & rhs) const { if (val != rhs.val) return val < rhs.val; else return id < rhs.id; } }; vector<struct Node>res; void work() { num = 0; memset(first, 0, sizeof first); int n; scanf("%d", &n); int root = 1; for (int i = 2; i <= n; ++i) { int fa; scanf("%d", &fa); addEdge(fa, i); addEdge(i, fa); } for (int i = 1; i <= n; ++i) { res.push_back(Node(dfs(i, 0) + 1, i)); } // for (int i = 0; i <= n - 1; ++i) { // cout << res[i] << endl; // } sort(res.begin(), res.end()); int mi = res[0].val; printf("%d ", mi); for (int i = 0; i < res.size(); ++i) { if (mi == res[i].val) { printf("%d ", res[i].id); } else break; } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }