树学 题解

换根dp，维护dp数组：以某结点为根的时候的答案
维护_size数组：某结点为根的子树大小
第二次dfs的时候换根进行旋转就可以了，类似于AVL树和Splay Tree的旋转

#include <bits/stdc++.h>
using namespace std;
const int N=1000100;
#define ll long long
ll _size[N];
ll dp[N];
ll ans=1e17;
struct node
{
    int v,next;
}e[N<<1];
int cnt=0;
int head[N];
void add(int u,int v)
{
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int u,int pre)
{
    _size[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int to=e[i].v;
        if(to==pre) continue;
        dfs(to,u);
        _size[u]+=_size[to];
        dp[u]+=dp[to]+_size[to];
    }
}
void dfs2(int u,int pre)
{
    ans=min(ans,dp[u]);
    for(int i=head[u];i;i=e[i].next)
    {
        int to=e[i].v;
        if(to==pre) continue;
        int p1=_size[u];
        int p2=_size[to];
        int P1=dp[u];
        int P2=dp[to];
        dp[u]-=(dp[to]+_size[to]);
        _size[u]-=_size[to];
        _size[to]+=_size[u];
        dp[to]+=(dp[u]+_size[u]);
        dfs2(to,u);
        _size[u]=p1;
        _size[to]=p2;
        dp[u]=P1;
        dp[to]=P2;
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs(1,-1);
    dfs2(1,-1);
    printf("%lld\n",ans);
}