简答题 偏难
#22103

day2-3 树的重心

day2-3 树的重心


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; typedef long long ll; const int MAXN = 3e5 + 10; vector&lt;int&gt; adj[MAXN]; // 计算以u为根,排除exclude节点的子树大小 int compute_size(int u, int parent, int exclude) {     int s = 1;     for (int v : adj[u]) {         if (v != parent &amp;&amp; v != exclude) {             s += compute_size(v, u, exclude);         }     }     return s; } // 查找以root为根,排除exclude节点的子树的所有重心 vector&lt;int&gt; find_centroids(int root, int exclude, int total_size) {     vector&lt;int&gt; centroids;     function&lt;void(int, int, int&amp;)&gt; dfs = [&amp;](int u, int p, int&amp; current_size) {         current_size = 1;         int max_sub = 0;         for (int v : adj[u]) {             if (v != p &amp;&amp; v != exclude) {                 int child_size = 0;                 dfs(v, u, child_size);                 current_size += child_size;                 max_sub = max(max_sub, child_size);             }         }         max_sub = max(max_sub, total_size-current_size);         if (max_sub &lt;= total_size / 2) {             centroids.push_back(u);         }     };     int dummy = 0;     dfs(root, exclude, dummy);     return centroids; } ll solve() {     int n;     cin &gt;&gt; n;     for (int i = 1; i &lt;= n; ++i) adj[i].clear();     vector&lt;pair&lt;int, int&gt;&gt; edges;     for (int i = 0; i &lt; n-1; ++i) {         int u, v;         cin &gt;&gt; u &gt;&gt; v;         adj[u].push_back(v);         adj[v].push_back(u);         edges.emplace_back(u, v);     }     ll ans = 0;     for (auto&amp; e : edges) {         int u = e.first, v = e.second;         // 计算分割后两个子树的大小         int s = compute_size(u, -1, v);         int t = n-s;         // 查找两个子树的重心         vector&lt;int&gt; c1 = find_centroids(u, v, s);         vector&lt;int&gt; c2 = find_centroids(v, u, t);         // 累加重心编号         for (int x : c1) ans += x;         for (int x : c2) ans += x;     }     return ans; } int main() {     ios::sync_with_stdio(false);     cin.tie(0);     int T;     cin &gt;&gt; T;     while (T--) {         cout &lt;&lt; solve() &lt;&lt; '\n';     }     return 0; }</pre><p><br/></p>
解析

方法思路

1、子树大小计算:对于每条边,删除后会得到两个子树,需要分别计算这两个子树的大小。

2、重心查找:对于每个子树,遍历其所有节点,判断每个节点是否为该子树的重心。判断条件是:删除该节点后,其所有子树的大小(包括父方向的子树)均不超过子树总大小的一半。

3、遍历所有边:对每条边,分别处理分割后的两个子树,找到各自的重心并求和,最终累加所有边的结果。

代码解释

1、compute_size函数:计算以u为根,排除exclude节点的子树大小。通过递归遍历子树,累加所有子节点的大小(排除父节点和exclude节点)。

2、find_centroids函数:查找以root为根,排除exclude节点的子树的所有重心。使用深度优先搜索(DFS)遍历子树,计算每个节点的最大子树大小(包括父方向的子树大小),判断是否为重心。

3、solve函数:处理每组测试用例,读取树的结构,遍历每条边,计算分割后两个子树的大小,查找各自的重心并累加结果。

该方法通过递归和深度优先搜索高效处理每个子树的重心查找,确保了时间复杂度在合理范围内,能够处理题目给定的数据规模。