算法
(树的直径、树上dfs) $O(N)$
结论:
若 $(a, b)$ 为树上某一直径的两端点,对于树上某任意一点 $v$,距离 $v$ 最远的点或者是 $a$,或者是 $b$。
利用上面的结论,我们可以很容易解决本题
而树的直径可以通过跑两遍dfs
解决
但这里涉及到了点权,所以我们在求直径的时候需要考虑每点的点权
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::max;
using std::vector;
using ll = long long;
using P = std::pair<ll, int>;
struct Edge {
int to, cost;
Edge() {}
Edge(int to, int cost): to(to), cost(cost) {}
};
int main() {
int n;
cin >> n;
vector<vector<Edge>> g(n);
rep(i, n-1) {
int a, b, c;
cin >> a >> b >> c;
--a; --b;
g[a].emplace_back(b, c);
g[b].emplace_back(a, c);
}
vector<int> x(n);
rep(i, n) cin >> x[i];
auto dfs = [&](auto& f, int v, ll d=0, int p=-1) -> P {
P res(d+x[v], v);
if (p == -1) res = P(-1, -1);
for (auto e : g[v]) {
int u = e.to;
if (u == p) continue;
res = max(res, f(f, u, d+e.cost, v));
}
return res;
};
int a = dfs(dfs, 0).second;
int b = dfs(dfs, a).second;
vector<ll> ans(n);
auto dfs2 = [&](auto& f, int v, ll d=0, int p=-1) -> void {
if (p != -1) ans[v] = max(ans[v], d);
for (auto e : g[v]) {
int u = e.to;
if (u == p) continue;
f(f, u, d+e.cost, v);
}
};
dfs2(dfs2, a, x[a]);
dfs2(dfs2, b, x[b]);
rep(i, n) cout << ans[i] << '\n';
return 0;
}