牛客 - 树学 （换根）

传送门：牛客 - 树学

思路分析

父亲与儿子之间的深度关系是+1，所以父亲的答案可以由儿子转移过来
儿子对父亲的贡献为儿子的答案+儿子的节点数
换根的时候先保留原始数据，然后计算新根的贡献，往下dfs，最后还原

样例输入

4
1 2
1 3
1 4

样例输出

3

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
 
using namespace std;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int INF = 0x3f3f3f3f;
const int N=1e6+10;
 
vector<int>e[N];
int dp[N],siz[N],f[N];
 
void dfs1(int u,int fa){
    siz[u]=1;
    for(auto v:e[u]){
        if(v==fa) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        dp[u]+=dp[v]+siz[v];
    }
}
 
void dfs2(int u,int fa){
    f[u]=dp[u];
    for(auto v:e[u]){
        if(v==fa) continue;
        int su=siz[u],sv=siz[v];
        int sdu=dp[u],sdv=dp[v];
        dp[u]-=(dp[v]+siz[v]);
        siz[u]-=siz[v];
        siz[v]+=siz[u];
        dp[v]+=dp[u]+siz[u];
        dfs2(v,u);
        siz[u]=su;
        siz[v]=sv;
        dp[u]=sdu;
        dp[v]=sdv;
    }
}
 
int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
 
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(1,1);
    dfs2(1,1);
    int ans=INF;
    for(int i=1;i<=n;i++) ans=min(ans,f[i]);
    cout<<ans<<endl;
 
 
 
 
    return 0;
}