发现网上都是o(nlogn)的写法，没有o(n)的，所以这里贴一下代码，简单讲解一下（感觉好像很难讲明白，我实在是太菜了QAQ）
显然如果派出一支军队访问子树，并回到子树根节点，那消耗的时间就是边长的2倍。首先，显然军队从根出发，经过一些路径后停留在叶子节点明显最优。考虑多引一支军队到达叶子节点，则该军队会先走过一段被其他军队走过的路径，会额外消耗一些时间。到达子树根节点后，子树根节点到某个叶子节点这段只用走一次，可以节省这段路径长度的时间。
dp[x]表示只考虑x节点所在的子树以及x指向父亲的那条边，至少多派一支军队走到x所在子树的叶子节点（且已经有其他军队进过x子树的父亲节点，且之前没有任何一个军队会走到x子树的叶子节点），最少会多消耗多少时间（负数表示能节省时间）。
转移的时候，如果有子树额外引一支军队能节省时间（即dp值小于0），那显然引一个军队走到该子树会使答案更优，如果没有任何一支军队dp值小于0，则选额外消耗时间最少的那一颗子树多派一支军队
#include<bits/stdc++.h>using namespace std;int dp[1001000];
int n;
vector<int>edg[1001000];
int Ti = 0;
void dfs(int now, int d) {if(edg[now].size() == 0) {dp[now] = (d-1) - 1;return;}int sum = 0;int num = 0;int minn = 10000000;for (int i = 0; i < edg[now].size(); i++) {int nex = edg[now][i];dfs(nex, d+1);if (dp[nex] <= 0) {num++;sum+=dp[nex];}minn = min(minn, dp[nex]);}if (num > 0) {dp[now] = sum - 2;} else {dp[now] = minn - 2;}
}void solve(){Ti++;scanf("%d",&n);for (int i = 1; i <= n; i++) {edg[i].clear();dp[i] = 0;}for (int i = 2; i <= n; i++) {int u;scanf("%d",&u);edg[u].push_back(i);}dfs(1, 0);int ans = 0;for (int i = 0;i < edg[1].size(); ++i) {if (dp[edg[1][i]] < 0) {ans += dp[edg[1][i]]; }}ans+= 2*(n-1);printf("Case #%d: %d\n",Ti,ans);
}int main(){int T;scanf("%d",&T);while(T--) {solve();}
}