给一棵有根树， 每个叶子节点上有一只蚂蚁。 在0时刻蚂蚁开始向上爬， 同一时刻， 除了根节点以外， 一个节点上面不能有2个蚂蚁。 问所有的蚂蚁都爬到根节点需要的最短时间。
因为除了根节点， 一个节点上面只能有一个蚂蚁， 所以我们将根节点去掉， 于是就有了一个森林。 时间就是所有子树里面花费时间最多的那棵树的时间。
对于每棵子树， 我们将所有的节点标一个深度， 然后将深度排序。 可以知道 dp[i] = max(dp[i-1]+1, d[i])， d是深度， 这样就可以求得最终答案。
#include <iostream> #include <vector> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <map> #include <set> #include <string> #include <queue> #include <stack> #include <bitset> using namespace std; #define pb(x) push_back(x) #define ll long long #define mk(x, y) make_pair(x, y) #define lson l, m, rt<<1 #define mem(a) memset(a, 0, sizeof(a)) #define rson m+1, r, rt<<1|1 #define mem1(a) memset(a, -1, sizeof(a)) #define mem2(a) memset(a, 0x3f, sizeof(a)) #define rep(i, n, a) for(int i = a; i<n; i++) #define fi first #define se second typedef pair<int, int> pll; const double PI = acos(-1.0); const double eps = 1e-8; const int mod = 1e9+7; const int inf = 1061109567; const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; const int maxn = 5e5+5; int head[maxn*2], num, cnt, dp[maxn], d[maxn]; struct node { int to, nextt, w; }e[maxn*2]; void add(int u, int v) { e[num].to = v, e[num].nextt = head[u], head[u] = num++; } void init() { num = 0; mem1(head); } void dfs(int u, int fa, int depth) { int flag = 0; for(int i = head[u]; ~i; i = e[i].nextt) { int v = e[i].to; if(v == fa) continue; flag = 1; dfs(v, u, depth+1); } if(!flag) { d[cnt++] = depth; } } int main() { init(); int n, u, v, ans = 0; cin>>n; for(int i = 1; i<n; i++) { scanf("%d%d", &u, &v); add(u, v); add(v, u); } for(int i = head[1]; ~i; i = e[i].nextt) { int v = e[i].to; cnt = 0; dfs(v, 1, 1); sort(d, d+cnt); for(int j = 1; j<cnt; j++) { d[j] = max(d[j-1]+1, d[j]); } ans = max(ans, d[cnt-1]); } cout<<ans<<endl; return 0; }
codeforces 622E. Ants in Leaves
原文：http://www.cnblogs.com/yohaha/p/5213931.html