P1395 会议【洛谷算法习题】

P1395 会议

网页链接

P1395 会议

题目描述

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

输入格式

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

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

输出格式

一行输出两个数字x xx和y yy。

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

y yy表示距离之和的最小值。

输入输出样例 #1

输入 #1

4 1 2 2 3 3 4

输出 #1

2 4

说明/提示

数据范围

对于70 % 70\%70%数据n ≤ 10 3 n \le 10^3n≤103。

对于100 % 100\%100%数据n ≤ 5 × 10 4 n \le 5 \times 10^4n≤5×104。

解题思路

本题是树的最小距离和重心经典问题，采用二次扫描与换根DP的方法，通过两次深度优先遍历在线性时间内求出所有节点的总距离和，进而找到最优会议地点。

核心原理：换根公式

对于树上任意相邻的父节点u uu与子节点v vv，当根从u uu切换到v vv时，距离和的变化是固定的：

• v vv子树内的所有节点到新根的距离全部减少 1，共s i z e [ v ] size[v]size[v]个节点，总距离和减少s i z e [ v ] size[v]size[v]；
• 不在v vv子树内的所有节点到新根的距离全部增加 1，共n − s i z e [ v ] n-size[v]n−size[v]个节点，总距离和增加n − s i z e [ v ] n-size[v]n−size[v]。

由此得到换根递推公式：
f [ v ] = f [ u ] − s i z e [ v ] + ( n − s i z e [ v ] ) f[v] = f[u] - size[v] + (n - size[v])f[v]=f[u]−size[v]+(n−size[v])
通过该公式可以由父节点的总距离和，以O ( 1 ) O(1)O(1)时间推导出子节点的总距离和，避免了对每个点单独BFS/DFS的高开销。

算法步骤

1. 邻接表建图：使用链式前向星存储无向树的双向边，适配5万节点的规模。
2. 后序DFS计算子树大小：从1号根节点出发递归遍历，统计每个节点的子树节点数。代码中hasn[x]表示子树中除自身外的节点总数，即s i z e [ x ] = h a s n [ x ] + 1 size[x] = hasn[x] + 1size[x]=hasn[x]+1。
3. 计算根节点的总距离和：从根节点出发深度遍历，累加所有节点的深度（到根的距离），得到根节点的总距离和f [ 1 ] f[1]f[1]。
4. 前序DFS执行换根DP：从根的子节点开始，利用换根公式计算每个子节点的总距离和，再递归向下处理所有子节点，最终得到全部节点的总距离和。
5. 筛选最优解：遍历所有节点，找到总距离和最小的节点；若存在多个最小值，保留编号最小的节点。

算法总时间复杂度为O ( n ) O(n)O(n)，完全适配n ≤ 5 × 10 4 n \le 5\times10^4n≤5×104的数据规模。

总结

核心逻辑：利用换根DP将每个点的距离和计算从O(n)优化为O(1)，两次DFS即可线性求解全节点的距离和，找到最小距离和对应的重心。
关键操作：子树大小统计、根节点距离和计算、换根公式递推、全局最小值按编号优先级筛选。
效率保障：仅两次线性遍历树结构，无冗余计算，五万级节点可毫秒级完成。

代码简要说明

1. 链式前向星存图：h数组存储每个节点的边表头，to存储边的终点，la存储同节点下一条边的索引，add函数实现双向加边。
2. dfs1函数：后序遍历计算子树大小，累加每个子树的节点数到hasn数组，返回子树中除自身外的节点总数。
3. dfs3函数：深度遍历计算根节点的总距离和，参数z为当前节点深度，累加所有节点深度到f[1]。
4. dfs2函数：前序遍历执行换根DP，通过父节点的f值代入公式计算当前节点的f值，再递归处理所有子节点。
5. 主函数逻辑：读入数据建图，依次完成子树统计、根距离和计算、全节点换根DP；遍历所有节点筛选出距离和最小且编号最小的节点，输出结果。
6. 编号优先级处理：初始最优节点设为1号，从2号开始遍历，仅当距离和严格小于当前最优值时才更新，保证相等时保留小编号。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;constll P=50001;ll n,hasn[P],f[P],yy=1;ll u,v;ll tot,la[P*2],to[P*2],h[P];voidadd(ll x,ll y){to[++tot]=y;la[tot]=h[x];h[x]=tot;}lldfs1(ll x,ll y){for(ll i=h[x];i;i=la[i])if(to[i]!=y)hasn[x]+=1+dfs1(to[i],x);returnhasn[x];}voiddfs2(ll x,ll y){f[x]=f[y]-(hasn[x]+1)+(n-hasn[x]-1);for(ll i=h[x];i;i=la[i])if(to[i]!=y)dfs2(to[i],x);}voiddfs3(ll x,ll y,ll z){f[1]+=z;for(ll i=h[x];i;i=la[i])if(to[i]!=y)dfs3(to[i],x,z+1);}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf("%lld",&n);for(ll i=1;i<n;i++){scanf("%lld%lld",&u,&v);add(u,v);add(v,u);}dfs1(1,0);for(ll i=h[1];i;i=la[i])dfs3(to[i],1,1);for(ll i=h[1];i;i=la[i])dfs2(to[i],1);for(ll i=2;i<=n;i++)if(f[i]<f[yy])yy=i;printf("%lld %lld\n",yy,f[yy]);return0;}