Tree Distances I
思路
先考虑只算节点 \(1\) 的答案，我们发现如果要每个节点都这么算一次的话，绝对会
我们发现，这种算法的瓶颈在于必须要每个节点都算一遍，而每算一遍都需要 \(O(n)\)，所以才会超时，那么可以思考如何快速的求出答案（总共 \(O(1)\) 是不肯能的，别妄想了），对于相连的两个点，似乎是存在一些关系的，比如：
设 \(f_u\) 为 \(u\) 的答案，\(g_u\) 为子树根节点为 \(u\) 的子树深度。
节点 \(x\) 和他的父亲 \(y\)，那么如果知道 \(y\) 的答案，那么 \(x\) 的可能的答案可以是 \(f_y + 1\)。
但是我们知道 \(x\) 的答案还可以往下找，所以 \(x\) 的答案还可以是 \(g_x\)。
不过推到这里还不算完，因为如果说 \(f_y\) 的路径中包含 \(x\) 那么答案就不能是 \(f_y\) 了，因为 \(x\) 的答案的路径不可能折上去又折下来，所以重新设计：
设 \(f_{u,0}\) 为 \(u\) 的答案最大值，\(f_{u,1}\) 为 \(u\) 的答案次大值，\(g\) 不变。
那么如果说在 \(f_{y,0}\) 的路径中有 \(x\)，那么就可以用 \(f_{y,1}\) 来更新答案，否则用 \(f_{y,0}\)，然后就结了。
code
点击查看代码
#include <iostream>
#include <vector>
using namespace std;
const int MaxN = 2e5 + 10;
int f[MaxN][2], n;
vector<int> g[MaxN];
void S(int x, int fa) {
for (int i : g[x]) {
if (fa == i) continue;
S(i, x);
int w = f[i][0] + 1;
if (f[x][0] < w) {
f[x][1] = f[x][0], f[x][0] = w;
} else if (f[x][1] < w) {
f[x][1] = w;
}
}
}
void DFS(int x, int fa) {
for (int i : g[x]) {
if (i == fa) continue;
if (f[i][0] + 1 == f[x][0]) {
int w = f[x][1] + 1;
if (f[i][0] < w) {
f[i][1] = f[i][0], f[i][0] = w;
} else if (f[i][1] < w) {
f[i][1] = w;
}
} else {
int w = f[x][0] + 1;
if (f[i][0] < w) {
f[i][1] = f[i][0], f[i][0] = w;
} else if (f[i][1] < w) {
f[i][1] = w;
}
}
DFS(i, x);
}
}
int main() {
cin >> n;
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
S(1, -1);
DFS(1, -1);
for (int i = 1; i <= n; i++) {
cout << f[i][0] << " ";
}
return 0;
}
习题 Tree Distances II（更水的题）
由于父亲的答案被占用了，也不会影响统计答案，然后如果用父亲 \(y\) 的答案转移到儿子 \(x\) 的话，那么除了 \(x\) 的子树的其它所有节点到 \(x\) 的答案都要 \(+1\)，而 \(x\) 及以下的答案都要 $ - 1$，所以可以设 \(sum_i\) 为子树 \(i\) 的大小，然后可以推出：\(f_x=f_y+(sum_1-sum_x)-sum_x\)。
code
点击查看代码
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int MaxN = 2e5 + 10;
ll f[MaxN], sum[MaxN], n;
vector<int> g[MaxN];
ll S(int x, int fa) {
ll res = 0;
sum[x] = 1;
for (int i : g[x]) {
if (fa == i) continue;
res += S(i, x) + sum[i];
sum[x] += sum[i];
}
return res;
}
void DFS(int x, int fa) {
for (int i : g[x]) {
if (i == fa) continue;
f[i] = f[x] + (sum[1] - sum[i]) - sum[i];
DFS(i, x);
}
}
int main() {
cin >> n;
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
f[1] = S(1, -1);
DFS(1, -1);
for (int i = 1; i <= n; i++) {
cout << f[i] << " ";
}
return 0;
}