Educational Codeforces Round 7 - E. Ants in Leaves - JavaScript

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：http://www.codeforces.com/contest/622/problem/E

题意是给你一棵树，1为根，每个叶子节点有一个蚂蚁，移动到一个邻接节点时间耗费为1，一个节点上不能同时有1个以上的蚂蚁数目（除了根节点外），让你求最后一个蚂蚁到达根节点的最少的时间。

可以先dfs预处理每个叶子节点的深度dep[i]，然后把1节点邻接的节点当作一个子根，求这个子根所在的子树上蚂蚁到这个子根的最大的时间，除了子树上蚂蚁最早到达的时间为ans[0] ，其余子树上的蚂蚁为max(ans[i - 1] , dep[i] + 1)，最后的答案就是遍历1所相邻的子根所得到的答案取一个最大值。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + ;
bool ok[MAXN];
vector <int> G[MAXN] , ans; void dfs(int u , int par , int dep) {
if(G[u].size() == ) {
ans.push_back(dep + );
return ;
}
for(int i = ; i < G[u].size() ; i++) {
if(G[u][i] != par) {
dfs(G[u][i] , u , dep + );
}
}
} int main()
{
int n , v , u;
scanf("%d" , &n);
for(int i = ; i < n ; i++) {
scanf("%d %d" , &u , &v);
G[u].push_back(v);
G[v].push_back(u);
}
int len = G[].size() , res = , temp;
for(int i = ; i < len ; i++) {
dfs(G[][i] , , );
sort(ans.begin() , ans.end());
temp = ans[];
for(int j = ; j < ans.size() ; j++) {
temp = max(temp + , ans[j]);
}
res = max(res , temp);
ans.clear();
}
printf("%d\n" , res);
}