[Codeforces150E] Freezing with Style!

做法

显然可以二分答案,转化为这样一个问题:每个边的边权是正负一,判断是否有长度在 \(l\)\(r\) 之间的路径,权值之和非负。

从下往上合并,每次考虑当前点作为 lca 的情况,然后把子树合并,由于你合并时只需要考虑一个点子树中每个深度到根权值和最大的点,可以用长链剖分来维护深度信息。合并的时候顺便询问一下答案,长链剖分 + 线段树即可。

时间复杂度 \(\mathcal O(n \log^2n)\)

代码

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;
const int inf = 0x3f3f3f3f;

typedef pair<int,int> pi;

int n, L, R, ca, ru, rv;
int l[maxn], dep[maxn], dis[maxn], mx[maxn], son[maxn], e = 0;
int tot, ls[maxn*20], rs[maxn*20], trt[maxn];
pi T[maxn*20];

struct Edge {
int v, w, x;
} E[maxn<<1];

inline void addEdge(int u, int v, int w) {
E[e].v = v, E[e].x = l[u], E[e].w = w, l[u] = e++;
}

void dfs1(int u, int f) {
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (v != f) {
dep[v] = dep[u] + 1;
dfs1(v, u);
if (!son[u] || mx[v] > mx[son[u]]) son[u] = v, mx[u] = mx[v] + 1;
}
}
}

void dfs2(int u, int f) {
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (v != f) {
if (E[p].w >= ca) dis[v] = dis[u] + 1;
else dis[v] = dis[u] - 1;
dfs2(v, u);
}
}
}

void upd(int p, pi v, int l, int r, int &rt) {
if (!rt) {
rt = ++ tot;
ls[rt] = rs[rt] = 0;
T[rt] = pi(-inf, 0);
}
T[rt] = max(T[rt], v);
if (l == r) return;
int m = (l + r) >> 1;
if (p <= m) upd(p, v, l, m, ls[rt]);
else upd(p, v, m+1, r, rs[rt]);
}

pi qry(int L, int R, int l, int r, int rt) {
if (!rt) return pi(-inf, 0);
if (L <= l && r <= R) return T[rt];
int m = (l + r) >> 1;
pi ret(-inf, 0);
if (L <= m) ret = max(ret, qry(L, R, l, m, ls[rt]));
if (R > m) ret = max(ret, qry(L, R, m+1, r, rs[rt]));
return ret;
}

int _dis, _dep;

// rt2 -> rt1

void _dfs1(int t, int l, int r, int rt) {
if (!rt) return;
if (l == r) {
int lb = max(0, L + 2 * _dep - l), rb = min(n, R + 2 * _dep - l);
if (lb <= rb) {
pi res = qry(lb, rb, 0, n, t);
if (res.first + T[rt].first - 2 * _dis >= 0) {
ru = res.second, rv = T[rt].second;
}
}
return;
}
int m = (l + r) >> 1;
_dfs1(t, l, m, ls[rt]);
_dfs1(t, m+1, r, rs[rt]);
}

void _dfs2(int t, int l, int r, int rt) {
if (!rt) return;
if (l == r) {
upd(l, T[rt], 0, n, t);
return;
}
int m = (l + r) >> 1;
_dfs2(t, l, m, ls[rt]);
_dfs2(t, m+1, r, rs[rt]);
}

void Merge(int rt1, int rt2) {
_dfs1(rt1, 0, n, rt2);
_dfs2(rt1, 0, n, rt2);
}

void dfs3(int u, int f) {
trt[u] = 0;
upd(dep[u], pi(dis[u], u), 0, n, trt[u]);
if (son[u]) dfs3(son[u], u);
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (v != f && v != son[u]) {
dfs3(v, u);
_dis = dis[u], _dep = dep[u];
Merge(trt[son[u]], trt[v]);
}
}
_dis = dis[u], _dep = dep[u];
if (son[u]) {
Merge(trt[son[u]], trt[u]);
trt[u] = trt[son[u]];
}
}

// check ca
int check() {
dfs2(1, 0);
tot = ru = rv = 0;
dfs3(1, 0);
if (ru + rv) return 1;
return 0;
}

int main() {
memset(l, -1, sizeof(l));
scanf("%d%d%d", &n, &L, &R);
for (int i = 1; i < n; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
addEdge(u, v, w), addEdge(v, u, w);
}
dfs1(1, 0);
int l = 0, r = int (1e9), ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
ca = mid;
if (check()) {
ans = mid;
l = mid + 1;
} else r = mid - 1;
}
ca = ans;
check();
printf("%d %d\n", ru, rv);
return 0;
}