Codeforces Round#769(Div.2)E1+E2 Distance Tree

本文主要是介绍Codeforces Round#769(Div.2)E1+E2 Distance Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

树是无环的连通无向图。加权树具有分配给每条边的权重。两个顶点之间的距离是连接它们的路径上的最小权重之和。
给定一棵具有 n 个顶点的加权树，每条边的权重为 1。将 d(v) 表示为顶点 1 和顶点 v 之间的距离。
如果可以在任意两个顶点 a 和 b (1≤a,b≤n) 之间临时添加一条权重为 x 的边，则令 f(x) 为 max{d(v),1<=v<=n} 的最小可能值。请注意，经过此操作后，图不再是树。

对于从 1 到 n 的每个整数 x，求 f(x)。

输入
第一行包含一个整数 t (1≤t≤10⁴)——测试用例的数量。

每个测试用例的第一行包含一个整数 n (2≤n≤3000)。

接下来的 n-1 行中的每一行都包含两个整数 u 和 v (1≤u,v≤n)，表示顶点 u 和 v 之间存在一条边。保证给定的边形成一棵树。

保证所有测试用例的 n 总和不超过 3⋅10⁵。

输出
对于每个测试用例，在一行中打印 n 个整数，对于从 1 到 n 的所有 x，其中的第 x 个等于 f(x)。

题解

提示：
1.添加类型为 (1,v) 的边是最佳的。
2.尝试检查固定 x 的答案是否最多为 ans。
3.对于固定的 x 和答案 ans，求具有 depthv>ans 的节点之间的距离。
4.对于每个节点，找到两个具有最深子树的子节点。
让 $f_{ans}$ 为具有 $depth_{v}>ans$ 的两个节点之间的最大距离。如果对于某些 x 答案最多是 ans，那么 $ans≥depth 或 ⌈f_{ans/2}⌉+x≤ans$ ，因为我们可以添加一条边 (1,u)，其中 u 位于连接最远的两条路径的中间 $depth_{v}>ans$ 的节点。由于随着ans的增加 $f_{ans}$ 减少，我们可以使用二分搜索。另请注意，我们可以使用两个指针并在增加 x 时增加 ans。

如何计算 $f_{ans}$ ？让我们为每个节点找到它的两个具有最深子树的子节点。令 $a_{v}$ 和 b_{v} 为其子树的深度（a_{v}≥b_{v}）。如果没有足够的孩子，将此值设置为 $depth_{v}$ 。如果 $b_v>0，做f_{bv−1}:=max(f{bv−1},a_v+b_v−2⋅depth_{v})$ 。之后，将 i 从 n−2 迭代到 0 并执行 $f_i=max(f_i,f_{i+1})$ 。

时间复杂度：O(n) 或 O(nlogn)，二分查找。
E1:

#include <bits/stdc++.h>
using namespace std;vector<vector<int>> g;
vector<int> depth;
int max_dist;
int corr, curr;void dfs1(int v, int p, int h) {depth[v] = h;for(int to : g[v]) {if(to == p) {continue;}dfs1(to, v, h + 1);}
}void dfs2(int v, int p, int h) {if(h > max_dist && depth[v] > curr) {max_dist = h;corr = v;}for(int to : g[v]) {if(to == p) {continue;}dfs2(to, v, h + 1);}
}int main() {int t;cin >> t;while(t--) {int n;cin >> n;g.assign(n, {});depth.resize(n);for(int i = 0; i < n - 1; ++i) {int u, v;cin >> u >> v;--u, --v;g[u].push_back(v);g[v].push_back(u);}dfs1(0, 0, 0);curr = 0;for(int x = 1; x <= n; ++x) {while(true) {max_dist = -1;corr = -1;for(int i = 0; i < n; ++i) {if(depth[i] <= curr) {continue;}dfs2(i, i, 0);break;}if(corr == -1) {break;}int v = corr;max_dist = -1, corr = -1;dfs2(v, v, 0);if(max_dist > 2 * (curr - x)) {++curr;} else {break;}}cout << curr << ' ';}cout << '\n';}
}

E2:

#include <bits/stdc++.h>
using namespace std;vector<vector<int>> g;
vector<int> d;
int n;int dfs(int v, int p = -1, int cur_d = 0) {int a = cur_d, b = cur_d;for(int u: g[v]) {if(u == p) continue;int s_d = dfs(u, v, cur_d + 1);if(s_d > a) {b = a;a = s_d;} else if(s_d > b) {b = s_d;}}int i = min(a, b) - 1;if(i >= 0) {d[i] = max(d[i], a + b - 2 * cur_d + 1);}return a;
}void solve() {cin >> n;g.assign(n, {});d.assign(n, 0);for(int i = 0; i < n - 1; i++) {int a, b;cin >> a >> b;a--; b--;g[a].push_back(b);g[b].push_back(a);}int m_ans = dfs(0);for(int i = n - 2; i >= 0; i--) d[i] = max(d[i], d[i + 1]);int ans = 0;for(int k = 1; k <= n; k++) {while(ans < m_ans && d[ans] / 2 + k > ans) ans++;cout << ans << ' ';} cout << '\n';
}int main() {int T;cin >> T;while(T--) {solve();}
}