C++14(g++5.4) 解法, 执行用时: 936ms, 内存消耗: 60384K, 提交时间: 2020-03-20 09:59:47

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e6+5;
vector<int>pic[N];
ll ans;
int sz[N];
void dfs(int v,int p,int d)
{
    sz[v]=1;
    ans+=d;
    for(int i=0;i<pic[v].size();i++)
    {
        int u=pic[v][i];
        if(u!=p)
        {
            dfs(u,v,d+1);
            sz[v]+=sz[u];
        }
    }
}
int main()
{
    int n,u,v;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        pic[u].pb(v);
        pic[v].pb(u);
    }
    ans=0;
    dfs(1,0,0);
    for(int i=2;i<=n;i++)
        ans=min(ans,ans+(n-sz[i])-sz[i]);
    printf("%lld\n",ans);
    return 0;
}

C++ 解法, 执行用时: 740ms, 内存消耗: 60312K, 提交时间: 2021-07-01 19:40:04

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int dp[N];
vector<int>g[N];
int ans;
void dfs(int x,int fa,int d){
    ans+=d;
    dp[x]=1;
    for(auto &t:g[x]){
        if(t==fa)continue;
        dfs(t,x,d+1);
        dp[x]+=dp[t];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int n;cin>>n;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,-1,0);
    for(int i=2;i<=n;i++)
        ans=min(ans,ans+n-2*dp[i]);
    cout<<ans;
}