90pts WA6求大佬调试
查看原帖
90pts WA6求大佬调试
891245
R_aier楼主2023/8/23 21:48
#include <bits/stdc++.h>
#define AC return 0;
#define WA return
#define LOCAL
#define int long long
const int maxn = 2e6 + 10;
using namespace std;
int n, m, cnt,q;
int siz[maxn],f[maxn];
struct Edge
{
    int v,next;
    Edge(){}
    Edge(int v,int ne):v(v),next(ne){}
}e[maxn<<1];
int head[maxn];
void addedge(int u,int v)
{
    e[++cnt] = Edge(v, head[u]);
    head[u] = cnt;
    e[++cnt] = Edge(u, head[v]);
    head[v] = cnt;
}

void dfs1(int u,int fa)
{
    siz[u]=1;
    for(int i=head[u],v=e[i].v;i;i=e[i].next,v=e[i].v)
    {
        if(v==fa) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
    }
}
void dfs2(int u,int fa)
{
    for (int i = head[u], v = e[i].v; i; i = e[i].next, v = e[i].v)
    {
        if(v==fa)
            continue;
        f[v] = f[u] + (n - 2 * siz[v]);
        dfs2(v,u);
    }
}
int ans=1;
void solve()
{
    dfs1(1,0);
    dfs2(1,0);
    for(int i=1;i<=n;++i)
        if(f[i]>f[ans]) 
            ans=i;
    printf("%lld",ans);
}


void init()
{
    cin>>n;
    int u,v;
    for(int i=1;i<=n;++i)
    {
        scanf("%lld%lld", &u, &v);
        addedge(u,v);
    }
}


signed main()
{
#ifdef LOCAL
    freopen("P3478_6.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    init();
    solve();
    AC
}

2023/8/23 21:48
加载中...