答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e5 + 10;
vector<int> adj[MAXN];
// 计算以u为根,排除exclude节点的子树大小
int compute_size(int u, int parent, int exclude) {
int s = 1;
for (int v : adj[u]) {
if (v != parent && v != exclude) {
s += compute_size(v, u, exclude);
}
}
return s;
}
// 查找以root为根,排除exclude节点的子树的所有重心
vector<int> find_centroids(int root, int exclude, int total_size) {
vector<int> centroids;
function<void(int, int, int&)> dfs = [&](int u, int p, int& current_size) {
current_size = 1;
int max_sub = 0;
for (int v : adj[u]) {
if (v != p && 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 <= total_size / 2) {
centroids.push_back(u);
}
};
int dummy = 0;
dfs(root, exclude, dummy);
return centroids;
}
ll solve() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) adj[i].clear();
vector<pair<int, int>> edges;
for (int i = 0; i < n-1; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
edges.emplace_back(u, v);
}
ll ans = 0;
for (auto& e : edges) {
int u = e.first, v = e.second;
// 计算分割后两个子树的大小
int s = compute_size(u, -1, v);
int t = n-s;
// 查找两个子树的重心
vector<int> c1 = find_centroids(u, v, s);
vector<int> 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 >> T;
while (T--) {
cout << solve() << '\n';
}
return 0;
}</pre><p><br/></p>
解析:
方法思路
1、子树大小计算:对于每条边,删除后会得到两个子树,需要分别计算这两个子树的大小。
2、重心查找:对于每个子树,遍历其所有节点,判断每个节点是否为该子树的重心。判断条件是:删除该节点后,其所有子树的大小(包括父方向的子树)均不超过子树总大小的一半。
3、遍历所有边:对每条边,分别处理分割后的两个子树,找到各自的重心并求和,最终累加所有边的结果。
代码解释
1、compute_size函数:计算以u为根,排除exclude节点的子树大小。通过递归遍历子树,累加所有子节点的大小(排除父节点和exclude节点)。
2、find_centroids函数:查找以root为根,排除exclude节点的子树的所有重心。使用深度优先搜索(DFS)遍历子树,计算每个节点的最大子树大小(包括父方向的子树大小),判断是否为重心。
3、solve函数:处理每组测试用例,读取树的结构,遍历每条边,计算分割后两个子树的大小,查找各自的重心并累加结果。
该方法通过递归和深度优先搜索高效处理每个子树的重心查找,确保了时间复杂度在合理范围内,能够处理题目给定的数据规模。