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输入 #14 1 2 2 3 3 4输出 #12 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的高开销。算法步骤邻接表建图使用链式前向星存储无向树的双向边适配5万节点的规模。后序DFS计算子树大小从1号根节点出发递归遍历统计每个节点的子树节点数。代码中hasn[x]表示子树中除自身外的节点总数即s i z e [ x ] h a s n [ x ] 1 size[x] hasn[x] 1size[x]hasn[x]1。计算根节点的总距离和从根节点出发深度遍历累加所有节点的深度到根的距离得到根节点的总距离和f [ 1 ] f[1]f[1]。前序DFS执行换根DP从根的子节点开始利用换根公式计算每个子节点的总距离和再递归向下处理所有子节点最终得到全部节点的总距离和。筛选最优解遍历所有节点找到总距离和最小的节点若存在多个最小值保留编号最小的节点。算法总时间复杂度为O ( n ) O(n)O(n)完全适配n ≤ 5 × 10 4 n \le 5\times10^4n≤5×104的数据规模。总结核心逻辑利用换根DP将每个点的距离和计算从O(n)优化为O(1)两次DFS即可线性求解全节点的距离和找到最小距离和对应的重心。关键操作子树大小统计、根节点距离和计算、换根公式递推、全局最小值按编号优先级筛选。效率保障仅两次线性遍历树结构无冗余计算五万级节点可毫秒级完成。代码简要说明链式前向星存图h数组存储每个节点的边表头to存储边的终点la存储同节点下一条边的索引add函数实现双向加边。dfs1函数后序遍历计算子树大小累加每个子树的节点数到hasn数组返回子树中除自身外的节点总数。dfs3函数深度遍历计算根节点的总距离和参数z为当前节点深度累加所有节点深度到f[1]。dfs2函数前序遍历执行换根DP通过父节点的f值代入公式计算当前节点的f值再递归处理所有子节点。主函数逻辑读入数据建图依次完成子树统计、根距离和计算、全节点换根DP遍历所有节点筛选出距离和最小且编号最小的节点输出结果。编号优先级处理初始最优节点设为1号从2号开始遍历仅当距离和严格小于当前最优值时才更新保证相等时保留小编号。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll P50001;ll n,hasn[P],f[P],yy1;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 ih[x];i;ila[i])if(to[i]!y)hasn[x]1dfs1(to[i],x);returnhasn[x];}voiddfs2(ll x,ll y){f[x]f[y]-(hasn[x]1)(n-hasn[x]-1);for(ll ih[x];i;ila[i])if(to[i]!y)dfs2(to[i],x);}voiddfs3(ll x,ll y,ll z){f[1]z;for(ll ih[x];i;ila[i])if(to[i]!y)dfs3(to[i],x,z1);}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld,n);for(ll i1;in;i){scanf(%lld%lld,u,v);add(u,v);add(v,u);}dfs1(1,0);for(ll ih[1];i;ila[i])dfs3(to[i],1,1);for(ll ih[1];i;ila[i])dfs2(to[i],1);for(ll i2;in;i)if(f[i]f[yy])yyi;printf(%lld %lld\n,yy,f[yy]);return0;}