/ Randle /

记录详情

Accepted

/in/foo.cc: In function 'int main()':
/in/foo.cc:79:11: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     printf("%d\n", ans);
     ~~~~~~^~~~~~~~~~~~~
# 状态 耗时 内存占用
#1 Accepted 13ms 12.375 MiB
#2 Accepted 6ms 12.363 MiB
#3 Accepted 7ms 14.336 MiB
#4 Accepted 277ms 47.223 MiB
#5 Accepted 256ms 47.242 MiB
#6 Accepted 263ms 47.09 MiB
#7 Accepted 280ms 45.113 MiB
#8 Accepted 330ms 45.25 MiB
#9 Accepted 359ms 45.086 MiB
#10 Accepted 322ms 47.23 MiB

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i,l,r) for (int i=l; i<=r; i++)
#define drep(i,r,l) for (int i=r; i>=l; i--)
#define ll long long
#define pb push_bake
const int N = 1000008; 
int n, tot, head[N], h[N], fa[N], sum[N];
bool vis[N];
ll Down[N], Up[N]; 
int read()
{
    char c; int w = 1, num = 0;
    for (c = getchar(); !isdigit(c) && c != '+' && c != '-'; c = getchar());
    if (c == '-') c = getchar(), w = -1; 
    if (c == '+') c = getchar();
    for (; isdigit(c); c = getchar()) num = num * 10 + c - '0';
    return num * w; 
}
struct Node
{
    int next, node; 
}e[2 * N];
inline void add(int x, int y)
{
    e[++tot].next = head[x], head[x] = tot, e[tot].node = y;
    e[++tot].next = head[y], head[y] = tot, e[tot].node = x;
}
void topsort()
{
    int l = 1, r = 1;
    h[1] = 1; vis[1] = 1;
    while (l <= r)
    {
        int u = h[l++];
        for (int i = head[u], v; v = e[i].node, i; i = e[i].next)
        if (!vis[v])
        {
            vis[v] = 1;
            fa[v] = u;
            h[++r] = v;
        }
    }
}
int main()
{
    n = read();
    rep(i, 1, n - 1)
    {
        int u, v;
        u = read(); v = read();
        add(u, v);
    }  
    topsort();
    drep(k, n, 1)
    {
        int u = h[k];
        sum[u] = 1;
        for (int i = head[u], v; v = e[i].node, i; i = e[i].next)
        if (v != fa[u])
        {
            sum[u] += sum[v];
            Down[u] += Down[v] + sum[v];
        }
    }
    rep(k, 2, n)
    {
        int u = h[k];
        Up[u] += Up[fa[u]] + sum[1] - sum[fa[u]] + 1;
        Up[u] += Down[fa[u]] - Down[u] - sum[u] + sum[fa[u]] - sum[u] - 1; 
    }
    ll Max = 0; int ans;
    rep(i, 1, n) if (Up[i] + Down[i] > Max) Max = Up[i] + Down[i], ans = i;
    printf("%d\n", ans);
    return 0;
}

信息

递交者
类型
递交
题目
树的深度 T1
题目数据
下载
语言
C++
递交时间
2017-10-11 19:44:58
评测时间
2017-10-11 19:44:58
评测机
分数
100
总耗时
2116ms
峰值内存
47.242 MiB