题意
我们有 n 个珠子，我们可以选择一枚珠子作为我们的起点。然后我们可以选择用红线将新珠子与已有的珠子连起来，或者在用红线连起来的两个点间加入一个点，并将红线替换为两个蓝线。
蓝线的长度即为我们的分数，求最大得分。
思路
首先我们任意选取一个节点作为根。
那么一定会出现下图所示的的状况。
那么对于一个节点我们有两种情况，要么是两个蓝线的终点，要么不是，那么因此我们用 $F[u][0 / 1]$ 来表示。
其中 0 表示不是中点，1表示是中点。
那么我们的答案就可以像下面这样的更新，假设点 $v$ 为点 $u$ 的子节点，$len$ 为两点间的距离。 \(F[u][0] = \sum_v \max(F[v][0] ,F[v][1] + len) \\ F[u][1] = F[u][0] + \max_v(F[v][0] + len - \max(F[v][0] , F[v][1] + len))\) 为了方便观察，我们不妨定义 $div = div(u,v) = \max(F[v][0] , F[v][1] + len)$
那么方程也就变成了，如下的式子
\(F[u][0] = \sum_v \max div \\ F[u][1] = F[u][0] + \max_v (F[v][0] + len - div)\) 那么我们最终 $F[root][0]$ 就是以我们随意选择的点作为根的最大值。
由于以不同根作为最大值不同，因此我们需要定义另一个最大值，$G[u][0 / 1]$ 具体意义为以点 $u$ 为根的最大值。
那么我们发现对于 $u$ 节点的一颗子树 $v$ 而言。包括了两个部分。如下图所示。
我们假定我们已经知道 $G[u][0]$ 和 $G[u][1]$ 我们现在需要推导 $G[v][0]$ 与 $G[v][1]$
首先我们定义 $H[0 / 1]$ 表示当以 $v$ 为根的时候，$v$ 的子树为 $u$ 时候的 $F[u][0 / 1]$ 。
那么首先我们可以得知 \(H[0] = G[u][0] - div \\ H[1] = H[0] + \max_{x \in son(u)}(len(u , x) - div(u,x)) \\ 或者通过 G[u][1] 来写。 \\ H[1] = G[u][1] - div + other\) 我们发现，当且仅当 $len + F[v][0] - div$ 是所有 $u$ 的子树中最大的时候，我们的 $H[1]$ 才需要计算其剩余的子树最大值，所以我们不妨记录最大值与次大值$MX[u][0 / 1]$。 0 表示最大值 , 1 表示次大值。
如果写成第二个式子我们同样也可以发现如上的问题。
那么这样子我们的 $H[1]$ 就可以变成了如下的形式。其中注释部分也是成立的。
1
2
3
4
5
6
7
if(MX[u][0] == len + F[v][0] - div) {
H[1] = H[0] + MX[u][1];
// H[1] = G[u][1] - div - MX[u][0] + MX[u][1];
} else {
H[1] = H[0] + MX[u][0];
// H[1] = G[u][1] - div;
}
那么此时，我们就得到了以 $u$ 作为点 $v$ 的子树的 $H[0 / 1]$ 那么我们的 \(G[v][0] = F[v][0] + \max(H[0],H[1] + len)\)
然后我们再求出其作为子树是否可以更新 $MX$ 的值，最后更新 $G[v][1]$ 的值。
1
2
3
4
5
6
7
8
long long MXD = H[0] + len - max(H[0] , H[1] + len);
if(MXD > MX[u][0]) {
MX[u][1] = MX[u][0];
MX[u][0] = MXD;
} else if (MXD > MX[u][1]) {
MX[u][1] = MXD;
}
G[v][1] = G[v][0] + MX[u][0];
通过上述，我们发现其实 $G[v][1]$ 并不是必要的。
那么最终的代码就是
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
const int N = 2e5 + 10;
vector<pair<int, int>> E[N];
LL F[N][2];
LL G[N][2];
LL H[N][2];
LL MX[N][2];
void dfs(int u, int fa = -1) {
F[u][0] = 0;
MX[u][0] = MX[u][1] = F[u][1] = -(1ll << 40);
for (auto [v, len] : E[u]) {
if (v == fa) continue;
dfs(v, u);
F[u][0] += max(F[v][0], F[v][1] + len);
}
for (auto [v, len] : E[u]) {
if (v == fa) continue;
LL div = len + F[v][0] - max(F[v][0], F[v][1] + len);
if (div > MX[u][0]) {
MX[u][1] = MX[u][0];
MX[u][0] = div;
} else if (div > MX[u][1]) {
MX[u][1] = div;
}
}
F[u][1] = F[u][0] + MX[u][0];
}
void dfs2(int u, int fa = -1) {
for (auto [v, len] : E[u]) {
if (v == fa) continue;
H[u][0] = G[u][0] - max(F[v][0], F[v][1] + len);
LL div = len + F[v][0] - max(F[v][0], F[v][1] + len);
if (div == MX[u][0]) {
H[u][1] =
G[u][1] - MX[u][0] + MX[u][1] - max(F[v][0], F[v][1] + len);
} else {
H[u][1] = G[u][1] - max(F[v][0], F[v][1] + len);
}
G[v][0] = F[v][0] + max(H[u][0], len + H[u][1]);
int MXD = len + H[u][0] - max(H[u][0], H[u][1] + len);
if (MXD > MX[v][0]) {
MX[v][1] = MX[v][0];
MX[v][0] = MXD;
} else if (MXD > MX[v][1]) {
MX[v][1] = MXD;
}
G[v][1] = G[v][0] + MX[v][0];
dfs2(v, u);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int x, y, len;
cin >> x >> y >> len;
E[x].push_back({y, len});
E[y].push_back({x, len});
}
long long ans = -1;
// cerr << "ROOT = " << 1 << '\n';
dfs(1);
G[1][0] = F[1][0], G[1][1] = F[1][1];
dfs2(1);
for (int i = 1; i <= n; i++) {
// cerr << "I = " << i << " G = " << G[i][0] << '\n';
ans = max(G[i][0], ans);
}
cout << ans << '\n';
return 0;
}