洛谷 P1395 会议

【题目链接】

洛谷 P1395 会议

【题目考点】

1. 树形动规：树的重心

本题为求树的重心模板题

【解题思路】

树的重心：相比于树中其它结点，其所有的子树中结点数最多的子树的结点数最少，该结点就是这棵树的重心。
另一种定义：
结点的平衡值为以该结点为根的树的所有子树中结点数最多的子树的结点数。树的重心为平衡值最小的结点。

树中所有点到某个点的距离和中，到重心的距离和是最小的。
见树的重心相关证明

首先对无根树进行dfs，得到有根树，求出有根树中以每个结点为根的子树的结点数，该过程也是一个树形动规的过程。
状态定义：$si{z}_u$表示以结点u为根的子树的大小，即以结点u为根的子树的结点数量。
状态转移方程：以u为根的子树的大小为所有以u的孩子v为根的子树的大小加和，再加上1（结点u）。
$si{z}_u=\sum si{z}_v+1，v\in chil{d}_u$，$chil{d}_u$表示u的子结点构成的集合。

求出$siz$数组的同时，可以求树的重心。

状态定义：$d{p}_u$：结点u的平衡值。即结点u的所有子树最大的子树的大小。
状态转移方程：
无根树中结点u的子树，包括有根树中结点u的子树，以及结点u的“上方子树”。
上方子树指的是有根树中除了以u为根的子树外所有结点构成的子树，该上方子树的大小为$n-si{z}_u$。
因此dpu=max⁡{{sizv},n−sizu},v∈childudp_u = \max\{\{{siz_v}\}, n-siz_u\}, v\in child_udpu​=max{{sizv​},n−sizu​},v∈childu​

具体实现时，对树做dfs的过程中完成状态转移。尝试访问结点u的每个孩子，从结点u访问到孩子v时，先进行dfs(v)，搜索求出$si{z}_v$与$d{p}_v$，而后根据$si{z}_v$更新$si{z}_u$与$d{p}_u$。
在访问结点u的所有孩子后，再使用$n-si{z}_u$更新$d{p}_u$。
dfs结束求出$dp$数组。树的重心为平衡值最小的结点，那么求$dp$数组最小值的下标，即为树的重心cent。
本题还要求求出所有结点到重心的距离和，该过程可以使用树形动规完成、也可以使用深搜完成。
如果使用树形动规完成：
以重心cent为根进行深搜：
状态定义：$di{s}_u$，有根树中以u为根的子树中所有结点到u的距离加和。
状态转移方程：设v是u的一个孩子，那么v中所有结点到u的距离加和，为v中所有结点到v的距离加和$di{s}_v$。以v为根的子树中所有结点要想到达u，还要经过边(u,v)，边权为1。以v为根的子树共有$si{z}_v$个结点，因此总路径加和增加了$si{z}_v$。注意：由于整棵树的根发生了改变，因此要重新求$siz$数组。
所有结点到重心的路径加和为$di{s}_{cent}$

【题解代码】

解法1：树形动规 求树的重心。树形动规求路径加和。

#include <bits/stdc++.h>
using namespace std;
#define N 50005
int n, siz[N], dp[N], dis[N];//siz[u]：以u为根的树的结点数（的大小） dp[u]:以u为整棵树的根时最大子树的大小 
vector<int> edge[N];
void dfs(int u, int fa)
{siz[u] = 1;for(int v : edge[u]) if(v != fa){dfs(v, u);siz[u] += siz[v];dp[u] = max(dp[u], siz[v]);}dp[u] = max(dp[u], n-siz[u]);
}
void dfs2(int u, int fa)
{siz[u] = 1;for(int v : edge[u]) if(v != fa){dfs2(v, u);siz[u] += siz[v];dis[u] += dis[v]+siz[v];}
}
int main()
{int a, b, cent = 1;cin >> n;for(int i = 1; i < n; ++i){cin >> a >> b;edge[a].push_back(b);edge[b].push_back(a);	}dfs(1, 0);for(int i = 1; i <= n; ++i)if(dp[i] < dp[cent])cent = i;dfs2(cent, 0);cout << cent << ' ' << dis[cent]; return 0;
}

解法2：树形动规 求树的重心。深搜求路径加和。

#include <bits/stdc++.h>
using namespace std;
#define N 50005
int n, siz[N], dp[N], ans;//siz[u]：以u为根的树的结点数（的大小） dp[u]:以u为整棵树的根时最大子树的大小 
vector<int> edge[N];
void dfs(int u, int fa)
{siz[u] = 1;for(int v : edge[u]) if(v != fa){dfs(v, u);siz[u] += siz[v];dp[u] = max(dp[u], siz[v]);}dp[u] = max(dp[u], n-siz[u]);
}
void dfs2(int u, int fa, int len)//len：根到u的路径长度 
{ans += len;for(int v : edge[u]) if(v != fa)dfs2(v, u, len+1);
}
int main()
{int a, b, cent = 1;cin >> n;for(int i = 1; i < n; ++i){cin >> a >> b;edge[a].push_back(b);edge[b].push_back(a);	}dfs(1, 0);for(int i = 1; i <= n; ++i)if(dp[i] < dp[cent])cent = i;dfs2(cent, 0, 0);cout << cent << ' ' << ans; return 0;
}