K 树dp 场上想了一个不太对的排序办法，真正的排序方法应该是将子树按照最深深度从低到高进行排序。然后随便维护一个dp数组表示从根节点派遣若干士兵遍历完i子树所需要的最小时间，每次尝试用子树的结果更新他们共同父节点的信息：
如果某节点是叶子，那么用其深度作为结果； 如果某节点不是叶子，将子树按照上述顺序排序后，考虑子树v1可能对v2造成的贡献：当height[v1] + 2 <= dep[v2]，那么从v1的士兵原路返回会比重新派遣一个人过来更优，将结果减去差值，不断重复更新。每次只需要考虑子树$i$对子树${i + 1}$的贡献，这是因为子树序列是单调的，一旦到某个位置后重新派遣更优，之后的所有位置也一定是重新派遣更优。 cpp 1const int manx = 1e6 + 10; 2 3struct star{int to, next;}; 4int head[maxn], top = 0; 5star edge[maxn << 1]; 6 7void add(int u, int v){ 8 edge[top].to = v; 9 edge[top].next = head[u]; 10 head[u] = top++; 11} 12 13int dep[maxn], height[maxn]; 14void dfs(int x, int par){ 15 height[x] = 0; 16 for(int i = head[x]; ~i; i = edge[i].next){ 17 int to = edge[i].to; if(to == par) continue; 18 dep[to] = dep[x] + 1; 19 dfs(to, x); 20 height[x] = max(height[x], height[to] + 1); 21 } 22} 23 24//从根结点派遣若干人，遍历完i子树所需要的最小代价即为dp[i] 25bool cmp(int x, int y){return height[x] < height[y];} 26ll dp[maxn]; 27void sove(int now, int par){ 28 vector<int> vec; 29 for(int i = head[now]; ~i; i = edge[i].next){ 30 itn to = edge[i].to; if(to == par) continue; 31 vec.push_back(to); 32 sove(to, now); 33 } 34 sort(vec.begin(), vec.end(), cmp); 35 if(vec.empty()) dp[now] = dep[now]; 36 else{ 37 int top = (int)vec.size(); 38 for(auto x: vec) dp[now] += dp[x]; 39 fro(int i = 1; i < top; i++){ 40 if(height[vec[i - 1]] + 2 <= dep[vec[i]]){ 41 dp[now] -= dep[vec[i]] - height[vec[i - 1]] - 2; 42 } 43 } 44 } 45} 46 47int main(){ 48 // Fastin; 49 int _; scanf("%d", &_); fro(int __ = 1; __ <= _; __++){ 50 top = 0; 51 int n; scanf("%d", &n); 52 for(int i = 1; i <= n; i++){ 53 dp[i] = height[i] = dep[i] = 0; 54 head[i] = -1; 55 } 56 for(int i = 2; i <= n; i++){ 57 int x; scanf("%d", &x); 58 add(x, i); add(i, x); 59 } 60 dfs(1, 0); 61 sove(1, 0); 62 printf("Case #%d: %d\n", __, dp[1]); 63 } 64 return 0; 65} J 哈希与组合数学 感谢冯佬的指点qaq 不然我可能一年都调不出来这题…sro flukehn….
...