SSL 2668_根_dfs+bfs

发布于 2017-08-07  855 次阅读

题目描述

一天，小B得到了一棵n个节点的树。无聊至极的小B想要找出一个点，使得以这个点为根时，所有点的深度之和最大。但小B打开手机，发现他最爱的re:creator又更新啦，于是这个无聊的任务就交给你了。

思路

先钦定1为根，然后dfs找出以1为根的深度和，并同时求出每一个点的子节点的个数

显然然后用bfs进行换根即可

#include 
#include 
using namespace std;
#define maxn 1000005
struct edge
{
    int to, next;
}e[maxn * 2];
int son[maxn], tot = 0, ls[maxn * 2], f[maxn], ma = 0, ans, n;
int read()
{
    int x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch -'0'; ch = getchar();}
    return x;
}
__attribute__((optimize("-O2")))
int dfs(int dep, int x)
{
    f[x] = 1;
    int fl = 0;
    son[x] = 1;
    for (int i = ls[x]; i; i = e[i].next)
        if (f[e[i].to] == 0)
        {
            fl = 1;
            dfs(dep + 1, e[i].to);
            son[x] += son[e[i].to];
            tot += dep + 1;
        }
}
__attribute__((optimize("-O2")))
int bfs()
{
    queue t;
    queue state;
    ans = 1;
    ma = ans;
    t.push(1);
    state.push(tot);
    f[1] = 0;
    while (!t.empty())
    {
        int now = t.front(), ns = state.front();
        t.pop(); state.pop();
        for (int i = ls[now]; i; i = e[i].next)
            if (f[e[i].to] == 1)
            {
                f[e[i].to] = 0;
                int tt = ns - son[e[i].to] + (n - son[e[i].to]);
                t.push(e[i].to);
                state.push(tt);
                if (tt > ma)
                {
                    ans = e[i].to;
                    ma = tt;
                }
                if (tt == ma && ans > e[i].to)
                    ans = e[i].to;
            }
    }
}
int main()
{
    scanf("%d", &n);
    int l = 0;
    for (int i = 1; i < n; i++)
    {
        int x = read(), y = read();
        e[++l] = (edge) {y, ls[x]};
        ls[x] = l;
        e[++l] = (edge) {x, ls[y]};
        ls[y] = l;
    }
    dfs(0, 1);
    
    bfs();
    printf("%d\n", ans);
}

 

]]>