codeforces 622E. Ants in Leaves-白红宇

codeforces 622E. Ants in Leaves

阅读量：5265 次

发布时间：2019-06-14

本文共 1486 字，大约阅读时间需要 4 分钟。

给一棵有根树，每个叶子节点上有一只蚂蚁。在0时刻蚂蚁开始向上爬，同一时刻，除了根节点以外，一个节点上面不能有2个蚂蚁。问所有的蚂蚁都爬到根节点需要的最短时间。

因为除了根节点，一个节点上面只能有一个蚂蚁，所以我们将根节点去掉，于是就有了一个森林。时间就是所有子树里面花费时间最多的那棵树的时间。

对于每棵子树，我们将所有的节点标一个深度，然后将深度排序。可以知道 dp[i] = max(dp[i-1]+1, d[i])， d是深度，这样就可以求得最终答案。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 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
                 
                   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

转载于:https://www.cnblogs.com/yohaha/p/5213931.html

你可能感兴趣的文章