树学

题意:求解最小的 ,由于根节点的不同,所以可以改变 值
题解:
1.

• 暴力搜索,以每个不同的点进行搜索值
  时间复杂度: ,超时

2.

• 以1节点为根节点,遍历全图,并且记录1节点的 值,相邻两个节点的 值,可以相互转化比如已知 求 , 两个节点相邻, 并且 距离1节点距离更近那么, ,其中 表示第 个节点的子节点个数并且包含其本身,那么是否相当于所有非其子节点的节点全部+1,其子节点全部-1
  时间复杂度:

code:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
list<int>mp[N];
int siz[N];
int n,u1,v1;
long long ans[N],minn=1e18;
void dfs(int u,int f)
{
    siz[u]=1;
    for(int v:mp[u])
    {
        if(v==f)
            continue;
        dfs(v,u);
        siz[u]+=siz[v];
        ans[u]+=ans[v]+siz[v];
    }
}
void dfs1(int u,int f)
{
    minn = min(minn,ans[u]);
    for(int v:mp[u])
    {
        if(v==f)
            continue;
        int res = n-siz[v];
        ans[v] = ans[u]-siz[v]+res;
        dfs1(v,u);
    }
}
int main()
{

    scanf("%d",&n);
    for(int i=1; i<n; i++)
    {
        scanf("%d %d",&u1,&v1);
        mp[u1].push_back(v1);
        mp[v1].push_back(u1);
    }
    dfs(1,-1);
    dfs1(1,-1);
    printf("%lld\n",minn);
}