Luogu 3647 - [APIO2014]连珠线

较为繁琐的树形 $\mbox{DP}$ 。

不难发现除了根节点以外,不可能构成横向的蓝色三元组,一定是纵向的蓝色三元组。

令 $f_{i, 0/1}$ 表示以 $i$ 为根,其是否是三元组的中间点。三元组包括三个点,两条边,上下两点是可以和别的三元组重复的,关键是要记录两条边。

有方程:

即 $b_i$ 为上式的次大值。

考虑换根:

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
93
94
95
96
97
98
99
#include <bits/stdc++.h>

#define MAXN 200005
#define INF 0x3f3f3f3f

using namespace std;

int n, ans;
int head[MAXN], cnt;
int fa[MAXN], back[MAXN], f[MAXN][2], g[MAXN][2], ultmax[MAXN], submax[MAXN];

struct data {
int next, to, cost;
data(int next = 0, int to = 0, int cost = 0):next(next), to(to), cost(cost) {}
}edge[MAXN << 1];

int read() {
char c = getchar();
int x = 0, s = 1;
while (!isdigit(c)) {
s = c == '-' ? -1 : 1;
c = getchar();
}
while (isdigit(c)) {
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
}
return x * s;
}

void connect(int u, int v, int w) {
edge[++cnt] = data(head[u], v, w);
head[u] = cnt;
}

void DFS1(int u, int pre) {
fa[u] = pre;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to, w = edge[i].cost;
if (v == pre) {
back[u] = w;
continue;
}
DFS1(v, u);
f[u][0] += max(f[v][0], f[v][1] + w);
if (w + f[v][0] - max(f[v][0], f[v][1] + w) > ultmax[u]) {
submax[u] = ultmax[u];
ultmax[u] = w + f[v][0] - max(f[v][0], f[v][1] + w);
}
else if (w + f[v][0] - max(f[v][0], f[v][1] + w) > submax[u])
submax[u] = w + f[v][0] - max(f[v][0], f[v][1] + w);
}
f[u][1] = f[u][0] + ultmax[u];
}

void DFS2(int u) {
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to, w = edge[i].cost;
if (v == fa[u])
continue;
g[v][0] = f[u][0] - max(f[v][0], f[v][1] + w) + max(g[u][0], g[u][1] + back[u]);
int temp = max(w + f[v][0] - max(f[v][0], f[v][1] + w) == ultmax[u] ? submax[u] : ultmax[u], u == 1 ? -INF : back[u] + g[u][0] - max(g[u][0], g[u][1] + back[u]));
g[v][1] = g[v][0] + temp;
DFS2(v);
}
}

int main() {
memset(ultmax, 0xcf, sizeof(ultmax));
memset(submax, 0xcf, sizeof(submax));
n = read();
for (int i = 1; i < n; ++i) {
int u = read(), v = read(), w = read();
connect(u, v, w);
connect(v, u, w);
}
DFS1(1, 0);
DFS2(1);
for (int u = 1; u <= n; ++u) {
vector<int> temp;
int sum = 0;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to, w = edge[i].cost;
if (v == fa[u]) {
temp.push_back(g[u][0] + w - max(g[u][0], g[u][1] + w));
sum += max(g[u][0], g[u][1] + w);
}
else {
temp.push_back(f[v][0] + w - max(f[v][0], f[v][1] + w));
sum += max(f[v][0], f[v][1] + w);
}
}
sort(temp.begin(), temp.end());
ans = max(ans, sum);
if (temp.size() >= 2)
ans = max(ans, sum + temp[temp.size() - 1] + temp[temp.size() - 2]);
}
printf("%d\n", ans);
}