[Luogu 1395] 会议

Description

有一个村庄居住着n个村民，有n-1条路径使得这n个村民的家联通，每条路径的长度都为1。现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？若有多个节点都满足条件，则选择节点编号最小的那个点。

Input

第一行。一个数n，表示有n个村民。

接下来n-1行，每行两个数字a和b，表示村民a的家和村民b的家之间存在一条路径。

Output

一行输出两个数字x和y

x表示村长将会在哪个村民家中举办会议

y表示距离之和的最小值

Range

70% n<=1000

100% n<=50000

Solution

第一想法是求出每个点到根节点的距离，然后 $O(n^2)$ lca 瞎搞，但是会 T。

所以换 O(n) 的树形 dp。

不妨钦定以 1 为根。

记录 size[i] 表示 i 与 i 的子树的结点个数之和。

定义 d[i] 表示在点 i 开会的距离和。

定义 subtree(x) 表示以 x 为根的子树中点的集合。显然 subtree(x)∈n

那么对于树上的非根节点 x，设它的父亲为 y。

所以转移方程 d[x]=d[y]+(n-size[x])-size[x]=d[y]+n-2*size[x]

意思是，

① 考虑不在 subtree(x) 中的点，它们到 x 的距离和是它们到 y 的距离和加上 (n-size[x])

② 而对于那些在 subtree(x) 中的点，它们到 x 的距离和就是它们到 y 的距离和再减去 (size[x])

所以合并两式，d[x]=d[y]+n-2*size[x]

时间复杂度 O(n)

Code

// By YoungNeal

#include<cstdio>

#define N 50005

int d[N];

int f[N];

int n,cnt;

int size[N];

bool vis[N];

int head[N];

struct Edge{

    int to,nxt;

}edge[N<<];

void add(int x,int y){

    edge[++cnt].to=y;

    edge[cnt].nxt=head[x];

    head[x]=cnt;

}

void dfs1(int now){

    size[now]=;

    for(int i=head[now];i;i=edge[i].nxt){

        int to=edge[i].to;

        if(d[to]) continue;

        d[to]=d[now]+;

        dfs1(to);

        size[now]+=size[to];

    }

}

void dfs(int now,int fa){

    f[now]=f[fa]+n-*size[now];

    for(int i=head[now];i;i=edge[i].nxt){

        int to=edge[i].to;

        if(to==fa) continue;

        dfs(to,now);

    }

}

signed main(){

    scanf("%d",&n);

    for(int x,y,i=;i<n;i++){

        scanf("%d%d",&x,&y);

        add(x,y);add(y,x);

    }

    d[]=;

    dfs1();

    int maxn=,idx=;

    for(int i=;i<=n;i++) maxn+=d[i];

    maxn-=n;

    f[]=maxn;

    for(int i=head[];i;i=edge[i].nxt){

        int to=edge[i].to;

        dfs(to,);

    }

    for(int i=;i<=n;i++){

        if(f[i]<maxn) maxn=f[i],idx=i;

    }

    printf("%d %d",idx,maxn);

    return ;

}

秒客网