Điểm hẹn (Đề tự luyện HSG Tin 12 – Bài 5)
Đề bài
Điểm hẹn. Có $N$ ấp nối bởi $N - 1$ con kênh tạo thành một cây; kênh $i$ nối $u_i$, $v_i$, chèo xuồng mất $w_i$ phút. Thầy Sơn có $M$ học trò, học trò $j$ ở ấp $p_j$. Có $Q$ sự kiện:
1 j x: học trò $j$ dời nhà sang ấp $x$;2 l r: thầy chọn một ấp làm điểm hẹn cho các học trò $l, l+1, \dots, r$ sao cho thời gian chèo xuồng lâu nhất của một em tới điểm hẹn là nhỏ nhất; in ra thời gian đó.
Dữ liệu vào: dòng đầu $N, M, Q$ ($1 \le N, M, Q \le 10^5$); $N - 1$ dòng $u_i, v_i, w_i$ ($1 \le w_i \le 10^9$); một dòng $p_1, \dots, p_M$; $Q$ dòng sự kiện (có ít nhất một sự kiện loại 2).
Kết quả: với mỗi sự kiện loại 2, in đáp án trên một dòng.
- Subtask 1 (10%): $N, M, Q \le 300$.
- Subtask 2 (15%): $N, M, Q \le 3000$.
- Subtask 3 (15%): kênh $i$ nối ấp $i$ với ấp $i + 1$.
- Subtask 4 (25%): $w_i = 1$ với mọi $i$.
- Subtask 5 (35%): không có ràng buộc gì thêm.
Input
8 5 5
1 2 8
2 3 6
3 4 2
3 5 4
4 6 5
4 7 2
7 8 7
5 3 7 4 3
2 1 5
2 2 4
1 5 6
2 1 5
2 1 4Output
4
2
6
4Giải thích
Buổi 1 (các em ở ấp $5, 3, 7, 4, 3$): hẹn ở ấp $3$, các em mất $4, 0, 4, 2, 0$ phút. Buổi 2 (ấp $3, 7, 4$): hẹn ở ấp $4$, mất $2, 2, 0$. Sau đó học trò 5 dời sang ấp $6$. Buổi 3 (ấp $5, 3, 7, 4, 6$): hẹn ở ấp $4$, mất $6, 2, 2, 0, 5$ phút. Buổi 4: hẹn ở ấp $3$, lâu nhất $4$ phút.
Dành cho học viênNộp bài trên ClueOJ
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Điểm hẹnLời mở đầu
Đây là bài "trùm cuối" của đề. Mỗi câu hỏi yêu cầu: với tập $S$ gồm các ấp nhà của nhóm học trò, tìm ấp $x$ làm cho $\text{xa}(x) = \max_{s \in S} d(x, s)$ nhỏ nhất ($d$ là thời gian chèo xuồng giữa hai ấp). Làm thẳng thì mỗi câu hỏi phải thử $N$ ấp, mỗi ấp nhìn $|S|$ em — quá chậm. Trong khi đó nhóm học trò thay đổi liên tục (khoảng $[l, r]$ tuỳ ý, các em còn dời nhà). Bài có ba nút thắt, ta gỡ từng cái.
Nhận xét 0 – khoảng cách trên cây. Treo cây ở ấp $1$, gọi $wd[v]$ là tổng thời gian từ gốc tới $v$. Khi đó $d(u, v) = wd[u] + wd[v] - 2 \cdot wd[\text{lca}(u, v)]$. Một đường đi có thể dài tới $10^5 \cdot 10^9 = 10^{14}$ nên mọi khoảng cách phải là long long.
Nút thắt 1 – chỉ cần hai em. Gọi $(a, b)$ là cặp ấp xa nhau nhất trong $S$ ("đường kính" của tập $S$), $D = d(a, b)$. Khi đó với mọi ấp $x$:
$$\text{xa}(x) = \max_{s \in S} d(x, s) = \max\big(d(x, a),\ d(x, b)\big).$$Tức là em ở xa $x$ nhất luôn có thể chọn là $a$ hoặc $b$, dù $x$ ở đâu! Hình dưới minh hoạ: dù $x$ đứng ở đâu, các em khác đều không xa hơn em ở $a$ hoặc em ở $b$.
Em $s$ nào cũng phải "treo" vào đường $a$–$b$ bằng một nhánh không dài hơn phần đường kính tính từ chỗ treo, nếu không thì $s$ ghép với $a$ hoặc $b$ sẽ cho cặp xa hơn $D$.
Chứng minh (bổ đề hai đầu mút)
Giả sử có em $s$ với $d(x, s) > d(x, a)$ và $d(x, s) > d(x, b)$. Gọi $y$ là ấp trên đường $a$–$b$ gần $x$ nhất (đường từ $x$ tới $a$ và tới $b$ đều đi qua $y$). Gọi $z$ là ấp mà đường $x \to s$ tách khỏi đường $x \to y$.
• Nếu $z \ne y$: $d(z, s) > d(z, y) + d(y, b)$ (trừ hai vế của $d(x, s) > d(x, b)$ cho $d(x, z)$). Khi đó $d(s, a) = d(s, z) + d(z, y) + d(y, a) > d(y, b) + d(y, a) = D$ — mâu thuẫn vì $D$ là lớn nhất.
• Nếu $z = y$: $d(y, s) > \max(d(y, a), d(y, b))$. Đường $y \to s$ không thể đi chung cạnh đầu tiên với cả hướng $y \to a$ lẫn hướng $y \to b$; giả sử không chung với hướng $y \to b$, thì $d(s, b) = d(s, y) + d(y, b) > d(y, a) + d(y, b) = D$ — lại mâu thuẫn.
Nút thắt 2 – điểm hẹn nằm trên đường $a$–$b$. Theo bổ đề, ta cần chọn $x$ để $\max(d(x, a), d(x, b))$ nhỏ nhất. Nếu $x$ nằm ngoài đường $a$–$b$ thì kéo $x$ về điểm $y$ (như hình) làm cả hai khoảng cách cùng giảm. Trên đường $a$–$b$, đi từ $a$ sang, $d(x, a)$ tăng dần còn $d(x, b) = D - d(x, a)$ giảm dần: điểm tốt nhất là ấp gần điểm giữa nhất — một trong hai ấp kẹp điểm giữa đường. Đáp án luôn $\ge D / 2$.
Nút thắt 3 – ghép đường kính. Nếu tập $S_1$ có đường kính $(a_1, b_1)$ và $S_2$ có đường kính $(a_2, b_2)$ thì đường kính của $S_1 \cup S_2$ có hai đầu nằm trong $\{a_1, b_1, a_2, b_2\}$: chỉ cần so 6 cặp (thực ra là 2 đường kính cũ và 4 cặp chéo). Lý do: nếu cặp xa nhất là $u \in S_1$, $v \in S_2$ thì theo bổ đề (với $x = u$ trên tập $S_2$) có $d(u, v) \le d(u, c)$ với $c \in \{a_2, b_2\}$, lại theo bổ đề (với $x = c$ trên tập $S_1$) có $d(c, u) \le d(c, a_1)$ hoặc $d(c, b_1)$. Phép ghép này cho phép dùng segment tree trên dãy học trò!
Các bạn thử mô phỏng dưới đây: nhập cây (mỗi kênh "u v w", cách nhau dấu phẩy) và tập ấp $S$; mô phỏng tìm cặp xa nhất bằng hai lần "đo xa", rồi kiểm tra bổ đề ở từng ấp $x$.
Ví dụ nhanh:
Lộ trình năm cách làm:
Cách 1Thử mọi ấp · 10%Cách 2Hai lần đo xa mỗi câu · 25%Cách 3Đường thẳng: min/max · 40%Cách 4w = 1: segment tree đường kính · 50%Cách 5+ nhảy nhị phân tìm điểm giữa · 100%
Cách 1Thử mọi ấp làm điểm hẹn – O(N² + Q·N·M) · 10%
Tính trước bảng khoảng cách giữa mọi cặp ấp bằng cách DFS từ từng ấp ($O(N^2)$). Mỗi buổi học, thử từng ấp $v$ làm điểm hẹn, tính em xa nhất trong nhóm, lấy nhỏ nhất. Dời nhà thì chỉ cần gán lại $p_j$. Với $N, M, Q \le 300$ thì cỡ $2{,}7 \cdot 10^7$ phép tính.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n, m, q;
scanf("%d %d %d", &n, &m, &q);
vector<vector<pair<int, int>>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v, w; scanf("%d %d %d", &u, &v, &w);
g[u].push_back({v, w}); g[v].push_back({u, w});
}
// D[s][v] = thoi gian cheo xuong tu ap s toi ap v (DFS tu moi ap)
vector<vector<ll>> D(n + 1, vector<ll>(n + 1, -1));
for (int s = 1; s <= n; s++) {
vector<int> stk = {s}; D[s][s] = 0;
while (!stk.empty()) {
int u = stk.back(); stk.pop_back();
for (auto [v, w] : g[u])
if (D[s][v] < 0) { D[s][v] = D[s][u] + w; stk.push_back(v); }
}
}
vector<int> p(m + 1);
for (int j = 1; j <= m; j++) scanf("%d", &p[j]);
while (q--) {
int t, x, y; scanf("%d %d %d", &t, &x, &y);
if (t == 1) { p[x] = y; continue; }
ll best = LLONG_MAX;
for (int v = 1; v <= n; v++) { // thu tung ap lam diem hen
ll mx = 0;
for (int j = x; j <= y; j++) mx = max(mx, D[v][p[j]]);
best = min(best, mx);
}
printf("%lld\n", best);
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1]); q = int(data[2]); p = 3
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u = int(data[p]); v = int(data[p + 1]); w = int(data[p + 2]); p += 3
g[u].append((v, w)); g[v].append((u, w))
# D[s][v] = thoi gian cheo xuong tu ap s toi ap v
D = [None] * (n + 1)
for s in range(1, n + 1):
d = [-1] * (n + 1); d[s] = 0; stk = [s]
while stk:
u = stk.pop()
for v, w in g[u]:
if d[v] < 0:
d[v] = d[u] + w; stk.append(v)
D[s] = d
home = [0] + [int(x) for x in data[p:p + m]]; p += m
out = []
for _ in range(q):
t = data[p]; x = int(data[p + 1]); y = int(data[p + 2]); p += 3
if t == b"1":
home[x] = y; continue
best = -1
for v in range(1, n + 1): # thu tung ap lam diem hen
dv = D[v]
mx = max(dv[home[j]] for j in range(x, y + 1))
if best < 0 or mx < best:
best = mx
out.append(str(best))
print("\n".join(out))
main()Không gian$O(N^2)$
Thời gian$O(N^2 + Q \cdot N \cdot M)$
Cách 2Hai lần "đo xa" cho mỗi buổi – O(Q·N) · 25%
Dùng ngay Nút thắt 1 và 2. Với mỗi buổi học:
- DFS từ nhà em $l$, tìm em trong nhóm ở xa nhất: được $a$.
- DFS từ $a$, tìm em trong nhóm ở xa nhất: được $b$. Đây là cặp xa nhau nhất của nhóm (giống cách tìm đường kính cây bằng hai lần BFS/DFS mà các bạn đã biết — nó đúng cũng chính nhờ bổ đề hai đầu mút: em xa $p_l$ nhất là một đầu mút đường kính, và em xa một đầu mút nhất là đầu mút còn lại).
- DFS từ $b$. Khi đó $\text{xa}(x) = \max(d_a[x], d_b[x])$ với mọi ấp $x$, lấy nhỏ nhất.
Mỗi buổi chỉ tốn 3 lần DFS, $O(N + M)$. Với $N, M, Q \le 3000$: khoảng $3 \cdot 9 \cdot 10^6$ bước, chạy thoải mái.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, q;
vector<vector<pair<int, int>>> g;
// khoang cach tu ap s toi moi ap (DFS khong de quy)
void dfs(int s, vector<ll>& d) {
d.assign(n + 1, -1); d[s] = 0;
vector<int> stk = {s};
while (!stk.empty()) {
int u = stk.back(); stk.pop_back();
for (auto [v, w] : g[u])
if (d[v] < 0) { d[v] = d[u] + w; stk.push_back(v); }
}
}
int main() {
scanf("%d %d %d", &n, &m, &q);
g.assign(n + 1, {});
for (int i = 0; i < n - 1; i++) {
int u, v, w; scanf("%d %d %d", &u, &v, &w);
g[u].push_back({v, w}); g[v].push_back({u, w});
}
vector<int> p(m + 1);
for (int j = 1; j <= m; j++) scanf("%d", &p[j]);
vector<ll> d0, da, db;
while (q--) {
int t, l, r; scanf("%d %d %d", &t, &l, &r);
if (t == 1) { p[l] = r; continue; }
// lan 1: tu nha em l, tim em o xa nhat -> a
dfs(p[l], d0);
int a = p[l];
for (int j = l; j <= r; j++) if (d0[p[j]] > d0[a]) a = p[j];
// lan 2: tu a, tim em o xa nhat -> b
dfs(a, da);
int b = a;
for (int j = l; j <= r; j++) if (da[p[j]] > da[b]) b = p[j];
dfs(b, db);
// em xa ap x nhat luon la a hoac b
ll best = LLONG_MAX;
for (int x = 1; x <= n; x++) best = min(best, max(da[x], db[x]));
printf("%lld\n", best);
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1]); q = int(data[2]); p = 3
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u = int(data[p]); v = int(data[p + 1]); w = int(data[p + 2]); p += 3
g[u].append((v, w)); g[v].append((u, w))
home = [0] + [int(x) for x in data[p:p + m]]; p += m
def dfs(s): # khoang cach tu ap s toi moi ap
d = [-1] * (n + 1); d[s] = 0; stk = [s]
while stk:
u = stk.pop()
du = d[u]
for v, w in g[u]:
if d[v] < 0:
d[v] = du + w; stk.append(v)
return d
out = []
for _ in range(q):
t = data[p]; l = int(data[p + 1]); r = int(data[p + 2]); p += 3
if t == b"1":
home[l] = r; continue
d0 = dfs(home[l]) # lan 1: tu nha em l tim em xa nhat -> a
a = home[l]
for j in range(l, r + 1):
if d0[home[j]] > d0[a]:
a = home[j]
da = dfs(a) # lan 2: tu a tim em xa nhat -> b
b = a
for j in range(l, r + 1):
if da[home[j]] > da[b]:
b = home[j]
db = dfs(b)
best = min(max(x, y) for x, y in zip(da[1:], db[1:])) # em xa nhat luon la a hoac b
out.append(str(best))
print("\n".join(out))
main()Không gian$O(N + M)$
Thời gian$O(Q \cdot (N + M))$
Bẫy: điểm hẹn không nhất thiết là nhà của một em!
Nhiều bạn chỉ thử các ấp có học trò ở. Ví dụ của đề "tình cờ" có điểm hẹn tốt nhất đều trùng nhà một em, nhưng trong bộ test thì thường không: điểm hẹn tốt nhất là ấp gần điểm giữa đường $a$–$b$, ấp đó có thể chẳng có em nào ở.Cách 3Khi các ấp nằm trên một đường thẳng – O((M + Q) log M + Q log N) · 40%
Ở Subtask 3, ấp $i$ nối ấp $i + 1$: các ấp nằm dọc một con kênh dài. Đặt toạ độ $X[1] = 0$, $X[i + 1] = X[i] + w_i$. Khi đó $d(u, v) = |X[u] - X[v]|$ và cặp xa nhau nhất của nhóm chính là ấp có toạ độ nhỏ nhất ($lo$) và lớn nhất ($hi$).
- Segment tree trên dãy học trò lưu min và max toạ độ nhà: dời nhà là cập nhật một điểm, mỗi buổi là truy vấn đoạn $[l, r]$.
- Điểm giữa là $(lo + hi) / 2$. Chặt nhị phân tìm ấp $v$ đầu tiên có $2 X[v] \ge lo + hi$; đáp án là giá trị nhỏ hơn giữa $\max(X[v] - lo, hi - X[v])$ và cùng biểu thức đó với ấp $v - 1$. (So sánh $2X[v]$ với $lo + hi$ để khỏi phải chia, tránh số thực.)
Cây không phải đường thẳng thì quay về Cách 2.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, q;
vector<vector<pair<int, int>>> g;
void dfs(int s, vector<ll>& d) { // Cach 2
d.assign(n + 1, -1); d[s] = 0;
vector<int> stk = {s};
while (!stk.empty()) {
int u = stk.back(); stk.pop_back();
for (auto [v, w] : g[u])
if (d[v] < 0) { d[v] = d[u] + w; stk.push_back(v); }
}
}
int sz;
vector<ll> mn, mx; // segment tree min / max toa do nha
void upd(int i, ll x) {
i += sz; mn[i] = mx[i] = x;
for (i >>= 1; i; i >>= 1) { mn[i] = min(mn[2 * i], mn[2 * i + 1]); mx[i] = max(mx[2 * i], mx[2 * i + 1]); }
}
int main() {
scanf("%d %d %d", &n, &m, &q);
g.assign(n + 1, {});
bool path = true;
vector<ll> X(n + 1, 0); // X[i] = toa do ap i tren duong thang
for (int i = 1; i <= n - 1; i++) {
int u, v, w; scanf("%d %d %d", &u, &v, &w);
g[u].push_back({v, w}); g[v].push_back({u, w});
if (u != i || v != i + 1) path = false;
X[i + 1] = X[i] + w;
}
vector<int> p(m + 1);
for (int j = 1; j <= m; j++) scanf("%d", &p[j]);
if (path) {
sz = 1; while (sz < m) sz <<= 1;
mn.assign(2 * sz, LLONG_MAX); mx.assign(2 * sz, LLONG_MIN);
for (int j = 1; j <= m; j++) upd(j - 1, X[p[j]]);
while (q--) {
int t, l, r; scanf("%d %d %d", &t, &l, &r);
if (t == 1) { upd(l - 1, X[r]); continue; }
ll lo = LLONG_MAX, hi = LLONG_MIN;
for (int a = l - 1 + sz, b = r + sz; a < b; a >>= 1, b >>= 1) {
if (a & 1) { lo = min(lo, mn[a]); hi = max(hi, mx[a]); a++; }
if (b & 1) { --b; lo = min(lo, mn[b]); hi = max(hi, mx[b]); }
}
// ap dau tien co toa do >= diem giua (lo + hi) / 2, va ap ngay truoc no
int v = 1, e = n; // chat nhi phan: ap dau tien co 2*X[v] >= lo + hi
while (v < e) {
int md = (v + e) / 2;
if (2 * X[md] >= lo + hi) e = md; else v = md + 1;
}
ll best = max(X[v] - lo, hi - X[v]);
if (v > 1) best = min(best, max(X[v - 1] - lo, hi - X[v - 1]));
printf("%lld\n", best);
}
return 0;
}
vector<ll> d0, da, db; // con lai: Cach 2
while (q--) {
int t, l, r; scanf("%d %d %d", &t, &l, &r);
if (t == 1) { p[l] = r; continue; }
dfs(p[l], d0);
int a = p[l];
for (int j = l; j <= r; j++) if (d0[p[j]] > d0[a]) a = p[j];
dfs(a, da);
int b = a;
for (int j = l; j <= r; j++) if (da[p[j]] > da[b]) b = p[j];
dfs(b, db);
ll best = LLONG_MAX;
for (int x = 1; x <= n; x++) best = min(best, max(da[x], db[x]));
printf("%lld\n", best);
}
return 0;
}import sys
from bisect import bisect_left
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1]); q = int(data[2]); p = 3
g = [[] for _ in range(n + 1)]
path = True
X2 = [0] * (n + 1) # X2[i] = 2 * toa do ap i tren duong thang
for i in range(1, n):
u = int(data[p]); v = int(data[p + 1]); w = int(data[p + 2]); p += 3
g[u].append((v, w)); g[v].append((u, w))
if u != i or v != i + 1:
path = False
X2[i + 1] = X2[i] + 2 * w
home = [0] + [int(x) for x in data[p:p + m]]; p += m
out = []
if path:
sz = 1
while sz < m:
sz <<= 1
INF = 1 << 62
mn = [INF] * (2 * sz); mx = [-INF] * (2 * sz)
for j in range(m):
mn[sz + j] = mx[sz + j] = X2[home[j + 1]] // 2
for i in range(sz - 1, 0, -1):
mn[i] = min(mn[2 * i], mn[2 * i + 1]); mx[i] = max(mx[2 * i], mx[2 * i + 1])
X2[0] = -INF # chan duoi cho bisect
for _ in range(q):
t = data[p]; l = int(data[p + 1]); r = int(data[p + 2]); p += 3
if t == b"1":
i = sz + l - 1; mn[i] = mx[i] = X2[r] // 2; i >>= 1
while i:
mn[i] = min(mn[2 * i], mn[2 * i + 1]); mx[i] = max(mx[2 * i], mx[2 * i + 1]); i >>= 1
continue
lo = INF; hi = -INF; a = l - 1 + sz; b = r + sz
while a < b:
if a & 1:
lo = min(lo, mn[a]); hi = max(hi, mx[a]); a += 1
if b & 1:
b -= 1; lo = min(lo, mn[b]); hi = max(hi, mx[b])
a >>= 1; b >>= 1
v = bisect_left(X2, lo + hi, 1) # ap dau tien co 2*toa do >= lo + hi
xv = X2[v] // 2
best = max(xv - lo, hi - xv)
if v > 1:
xv = X2[v - 1] // 2
best = min(best, max(xv - lo, hi - xv))
out.append(str(best))
print("\n".join(out))
return
def dfs(s): # con lai: Cach 2
d = [-1] * (n + 1); d[s] = 0; stk = [s]
while stk:
u = stk.pop(); du = d[u]
for v, w in g[u]:
if d[v] < 0:
d[v] = du + w; stk.append(v)
return d
for _ in range(q):
t = data[p]; l = int(data[p + 1]); r = int(data[p + 2]); p += 3
if t == b"1":
home[l] = r; continue
d0 = dfs(home[l]); a = home[l]
for j in range(l, r + 1):
if d0[home[j]] > d0[a]:
a = home[j]
da = dfs(a); b = a
for j in range(l, r + 1):
if da[home[j]] > da[b]:
b = home[j]
db = dfs(b)
out.append(str(min(max(x, y) for x, y in zip(da[1:], db[1:]))))
print("\n".join(out))
main()Không gian$O(N + M)$
Thời gian$O((M + Q) \log M + Q \log N)$
Trên đường thẳng, "min và max" ghép lại rất dễ. Câu hỏi lớn: trên cây tổng quát, thông tin nào của một nhóm có thể ghép được như min/max? Câu trả lời chính là Nút thắt 3: cặp đường kính.
Cách 4Mọi kênh dài 1: segment tree ghép đường kính – O((M + Q) log M) · 50%
Mỗi nút của segment tree (trên dãy học trò $1..M$) lưu bộ ba $(a, b, D)$ = cặp ấp xa nhau nhất của các em trong đoạn nút quản lý và khoảng cách giữa chúng. Lá của học trò $j$ là $(p_j, p_j, 0)$. Ghép hai nút: lấy cặp có $D$ lớn hơn trong hai nút, rồi thử thêm 4 cặp chéo $(a_1, a_2), (a_1, b_2), (b_1, a_2), (b_1, b_2)$. Dời nhà = cập nhật một lá rồi ghép lại các nút tổ tiên; mỗi buổi = ghép các nút phủ đoạn $[l, r]$.
Mỗi lần ghép cần 4 lần tính khoảng cách, tức 4 lần tìm LCA. Ta dùng LCA $O(1)$: DFS đánh số thứ tự thăm $tin[v]$, rồi với $u \ne v$, $tin[u] < tin[v]$, ấp LCA chính là ấp có $tin$ nhỏ nhất trong các $tin[\text{cha}(w)]$ với $w$ được thăm trong đoạn thời gian $(tin[u], tin[v]]$. (Trong đoạn đó chắc chắn có con của LCA nằm trên đường xuống $v$, mà mọi ấp trong đoạn đều thuộc cây con của LCA.) Đây là bài toán min trên đoạn tĩnh — dùng bảng thưa (sparse table) trả lời $O(1)$.
Khi mọi kênh dài 1, trên đường $a$–$b$ (dài $D$ cạnh) luôn có ấp cách $a$ đúng $\lceil D/2 \rceil$ cạnh, nên đáp án là $\lceil D / 2 \rceil$ = (D + 1) / 2. Các test có trọng số khác thì dùng Cách 2.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, q;
vector<vector<pair<int, int>>> g;
vector<int> par, tin, ord_, lg;
vector<ll> wd;
vector<vector<int>> sp;
int lca(int u, int v) {
if (u == v) return u;
int l = tin[u], r = tin[v];
if (l > r) swap(l, r);
l++;
int k = lg[r - l + 1];
return ord_[min(sp[k][l], sp[k][r - (1 << k) + 1])];
}
ll dist(int u, int v) { return wd[u] + wd[v] - 2 * wd[lca(u, v)]; }
struct Node { int a, b; ll d; };
Node mergeN(const Node& x, const Node& y) {
Node r = x.d >= y.d ? x : y;
int P[2] = {x.a, x.b}, Qv[2] = {y.a, y.b};
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++) {
ll d = dist(P[i], Qv[j]);
if (d > r.d) r = {P[i], Qv[j], d};
}
return r;
}
void dfs(int s, vector<ll>& d) { // Cach 2
d.assign(n + 1, -1); d[s] = 0;
vector<int> stk = {s};
while (!stk.empty()) {
int u = stk.back(); stk.pop_back();
for (auto [v, w] : g[u])
if (d[v] < 0) { d[v] = d[u] + w; stk.push_back(v); }
}
}
int main() {
scanf("%d %d %d", &n, &m, &q);
g.assign(n + 1, {});
bool allOne = true;
for (int i = 0; i < n - 1; i++) {
int u, v, w; scanf("%d %d %d", &u, &v, &w);
g[u].push_back({v, w}); g[v].push_back({u, w});
if (w != 1) allOne = false;
}
vector<int> p(m + 1);
for (int j = 1; j <= m; j++) scanf("%d", &p[j]);
if (!allOne) { // con lai: Cach 2
vector<ll> d0, da, db;
while (q--) {
int t, l, r; scanf("%d %d %d", &t, &l, &r);
if (t == 1) { p[l] = r; continue; }
dfs(p[l], d0);
int a = p[l];
for (int j = l; j <= r; j++) if (d0[p[j]] > d0[a]) a = p[j];
dfs(a, da);
int b = a;
for (int j = l; j <= r; j++) if (da[p[j]] > da[b]) b = p[j];
dfs(b, db);
ll best = LLONG_MAX;
for (int x = 1; x <= n; x++) best = min(best, max(da[x], db[x]));
printf("%lld\n", best);
}
return 0;
}
// moi kenh dai 1: dap so = ceil(D / 2), D = duong kinh cua nhom
par.assign(n + 1, 0); tin.assign(n + 1, 0); wd.assign(n + 1, 0);
vector<int> stk = {1}; par[1] = 1;
vector<char> vis(n + 1, 0);
while (!stk.empty()) {
int u = stk.back(); stk.pop_back();
vis[u] = 1; tin[u] = ord_.size(); ord_.push_back(u);
for (auto [v, w] : g[u]) if (!vis[v]) { par[v] = u; wd[v] = wd[u] + w; stk.push_back(v); }
}
lg.assign(n + 2, 0);
for (int i = 2; i <= n + 1; i++) lg[i] = lg[i / 2] + 1;
sp.assign(lg[n] + 1, vector<int>(n));
for (int i = 0; i < n; i++) sp[0][i] = tin[par[ord_[i]]];
for (int k = 1; (1 << k) <= n; k++)
for (int i = 0; i + (1 << k) <= n; i++) sp[k][i] = min(sp[k - 1][i], sp[k - 1][i + (1 << (k - 1))]);
int sz = 1; while (sz < m) sz <<= 1;
vector<Node> st(2 * sz, {1, 1, 0});
for (int j = 0; j < m; j++) st[sz + j] = {p[j + 1], p[j + 1], 0};
for (int i = sz - 1; i >= 1; i--) st[i] = mergeN(st[2 * i], st[2 * i + 1]);
while (q--) {
int t, x, y; scanf("%d %d %d", &t, &x, &y);
if (t == 1) {
int i = sz + x - 1; st[i] = {y, y, 0};
for (i >>= 1; i >= 1; i >>= 1) st[i] = mergeN(st[2 * i], st[2 * i + 1]);
continue;
}
Node res = {-1, -1, -1};
for (int l = x - 1 + sz, r = y + sz; l < r; l >>= 1, r >>= 1) {
if (l & 1) { res = res.d < 0 ? st[l] : mergeN(res, st[l]); l++; }
if (r & 1) { --r; res = res.d < 0 ? st[r] : mergeN(res, st[r]); }
}
printf("%lld\n", (res.d + 1) / 2);
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1]); q = int(data[2]); p = 3
g = [[] for _ in range(n + 1)]
all_one = True
for _ in range(n - 1):
u = int(data[p]); v = int(data[p + 1]); w = int(data[p + 2]); p += 3
g[u].append((v, w)); g[v].append((u, w))
if w != 1:
all_one = False
home = [0] + [int(x) for x in data[p:p + m]]; p += m
out = []
if not all_one: # con lai: Cach 2
def dfs(s):
d = [-1] * (n + 1); d[s] = 0; stk = [s]
while stk:
u = stk.pop(); du = d[u]
for v, w in g[u]:
if d[v] < 0:
d[v] = du + w; stk.append(v)
return d
for _ in range(q):
t = data[p]; l = int(data[p + 1]); r = int(data[p + 2]); p += 3
if t == b"1":
home[l] = r; continue
d0 = dfs(home[l]); a = home[l]
for j in range(l, r + 1):
if d0[home[j]] > d0[a]:
a = home[j]
da = dfs(a); b = a
for j in range(l, r + 1):
if da[home[j]] > da[b]:
b = home[j]
db = dfs(b)
out.append(str(min(max(x, y) for x, y in zip(da[1:], db[1:]))))
print("\n".join(out))
return
# moi kenh dai 1: dap so = ceil(D / 2)
par = [0] * (n + 1); wd = [0] * (n + 1); tin = [0] * (n + 1)
order = []; vis = [False] * (n + 1)
par[1] = 1; stk = [1]
while stk:
u = stk.pop(); vis[u] = True
tin[u] = len(order); order.append(u)
for v, w in g[u]:
if not vis[v]:
par[v] = u; wd[v] = wd[u] + w; stk.append(v)
sp = [[tin[par[order[i]]] for i in range(n)]]
k = 1
while (1 << k) <= n:
prev = sp[-1]; h = 1 << (k - 1)
sp.append([min(prev[i], prev[i + h]) for i in range(n - (1 << k) + 1)])
k += 1
def dist(u, v):
if u == v:
return 0
l = tin[u]; r = tin[v]
if l > r:
l, r = r, l
l += 1
k = (r - l + 1).bit_length() - 1
row = sp[k]; x = row[l]; y = row[r - (1 << k) + 1]
return wd[u] + wd[v] - 2 * wd[order[x if x < y else y]]
def merge(a1, b1, d1, a2, b2, d2):
if d2 > d1:
a1, b1, d1, a2, b2, d2 = a2, b2, d2, a1, b1, d1
ra = a1; rb = b1; rd = d1
d = dist(a1, a2)
if d > rd: ra = a1; rb = a2; rd = d
d = dist(a1, b2)
if d > rd: ra = a1; rb = b2; rd = d
d = dist(b1, a2)
if d > rd: ra = b1; rb = a2; rd = d
d = dist(b1, b2)
if d > rd: ra = b1; rb = b2; rd = d
return ra, rb, rd
sz = 1
while sz < m:
sz <<= 1
SA = [1] * (2 * sz); SB = [1] * (2 * sz); SD = [0] * (2 * sz)
for j in range(m):
SA[sz + j] = SB[sz + j] = home[j + 1]
for i in range(sz - 1, 0, -1):
SA[i], SB[i], SD[i] = merge(SA[2 * i], SB[2 * i], SD[2 * i], SA[2 * i + 1], SB[2 * i + 1], SD[2 * i + 1])
for _ in range(q):
t = data[p]; x = int(data[p + 1]); y = int(data[p + 2]); p += 3
if t == b"1":
i = sz + x - 1; SA[i] = SB[i] = y; SD[i] = 0; i >>= 1
while i:
SA[i], SB[i], SD[i] = merge(SA[2 * i], SB[2 * i], SD[2 * i], SA[2 * i + 1], SB[2 * i + 1], SD[2 * i + 1])
i >>= 1
continue
l = x - 1 + sz; r = y + sz; a = b = -1; D = -1
while l < r:
if l & 1:
if D < 0: a = SA[l]; b = SB[l]; D = SD[l]
else: a, b, D = merge(a, b, D, SA[l], SB[l], SD[l])
l += 1
if r & 1:
r -= 1
if D < 0: a = SA[r]; b = SB[r]; D = SD[r]
else: a, b, D = merge(a, b, D, SA[r], SB[r], SD[r])
l >>= 1; r >>= 1
out.append(str((D + 1) // 2))
print("\n".join(out))
main()Không gian$O(N \log N + M)$
Thời gian$O(N \log N + (M + Q) \log M)$
Bẫy: "nửa đường kính làm tròn lên" chỉ đúng khi mọi kênh dài 1!
Với thời gian $w_i$ tuỳ ý, có thể không có ấp nào gần điểm giữa đường $a$–$b$. Chẳng hạn đường $a$–$b$ chỉ gồm một kênh dài $10$: chẳng có ấp nào ở giữa, đáp án là $10$ chứ không phải $5$. Ví dụ của đề lại "khéo" có ấp nằm đúng (hoặc rất sát) điểm giữa ở mọi buổi, nên in $\lceil D/2 \rceil$ vẫn đúng ví dụ — nhưng cách này chỉ được 27,9% điểm.Cách 5Nhảy nhị phân tìm ấp gần điểm giữa – O((N + M + Q) log) · 100%
Đã có $(a, b, D)$ của nhóm, ta cần tìm hai ấp kẹp điểm giữa đường $a$–$b$. Gọi $c = \text{lca}(a, b)$, $d_a = wd[a] - wd[c]$ (độ dài nhánh $a \to c$). Nếu $2 d_a < D$ thì điểm giữa nằm trên nhánh $b \to c$: đổi vai $a$ và $b$. Giờ điểm giữa nằm trên nhánh $a \to c$:
- Nhảy nhị phân từ $a$ lên tổ tiên cao nhất $u$ vẫn thỏa: $u$ không vượt quá $c$ (tức $dep[u] \ge dep[c]$) và $2 \cdot (wd[a] - wd[u]) \le D$ (chưa qua điểm giữa). Dùng bảng
up[k][v]= tổ tiên thứ $2^k$ của $v$. - Ứng viên 1 là $u$: $\max(d(a,u), d(u,b)) = D - d(a, u)$ vì $u$ chưa qua điểm giữa.
- Ứng viên 2 là cha của $u$ (nếu $u \ne c$): đã qua điểm giữa nên giá trị là $d(a, \text{cha}(u)) = wd[a] - wd[\text{cha}(u)]$.
Đáp án là giá trị nhỏ hơn. Mọi phép so sánh đều nhân 2 thay vì chia 2 để làm việc với số nguyên. Mô phỏng dưới đây chạy segment tree ghép đường kính và bước tìm điểm giữa trên cây của ví dụ (các bạn có thể sửa nhà các em và đoạn $[l, r]$):
Ví dụ nhanh:
Toàn bộ lời giải chuẩn. Bản Python dùng đúng ý tưởng trên (DFS không đệ quy, bảng thưa cho LCA, segment tree ghép đường kính, nhảy nhị phân), kèm vài mẹo để chạy nhanh với PyPy 3:
- mọi bảng đều là mảng phẳng (
sp[k*n + i],up[k*n + v]), không dùng danh sách lồng nhau hay hàm trả về bộ; - đánh số lại các ấp theo thứ tự thăm DFS, nên "thứ tự thăm" của ấp $u$ chính là $u$; bảng thưa lưu luôn $wd$ của cha nên min trên đoạn chính là $wd[\text{lca}]$;
- treo cây ở tâm của cả cây: khi đó $d(u, v) \le wd[u] + wd[v]$ là một cận trên khá sát, cặp nào có $wd[u] + wd[v]$ không vượt kết quả hiện tại thì bỏ qua, khỏi tìm LCA (bỏ được khoảng 80% số lần tìm LCA);
- khi dời nhà, đi lên từ lá và dừng sớm nếu một nút không đổi (các nút tổ tiên cũng không đổi).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LOG = 17;
int n, m, q;
vector<vector<pair<int, int>>> g;
vector<int> par, dep, tin, ord_, lg;
vector<ll> wd; // wd[v] = tong trong so tu goc toi v
vector<vector<int>> sp, up; // sp: bang thua cho LCA, up: nhay nhi phan
int lca(int u, int v) {
if (u == v) return u;
int l = tin[u], r = tin[v];
if (l > r) swap(l, r);
l++; // min tin[cha] tren doan (l, r] la tin[lca]
int k = lg[r - l + 1];
return ord_[min(sp[k][l], sp[k][r - (1 << k) + 1])];
}
ll dist(int u, int v) { return wd[u] + wd[v] - 2 * wd[lca(u, v)]; }
struct Node { int a, b; ll d; }; // cap xa nhat (a, b) cua tap, d = dist(a, b)
Node mergeN(const Node& x, const Node& y) {
Node r = x.d >= y.d ? x : y;
int P[2] = {x.a, x.b}, Qv[2] = {y.a, y.b};
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++) {
ll d = dist(P[i], Qv[j]);
if (d > r.d) r = {P[i], Qv[j], d};
}
return r;
}
vector<Node> st;
int sz;
void upd(int pos, int v) {
pos += sz; st[pos] = {v, v, 0};
for (pos >>= 1; pos >= 1; pos >>= 1) st[pos] = mergeN(st[2 * pos], st[2 * pos + 1]);
}
Node query(int l, int r) { // [l, r) chi so tu 0
Node res = {-1, -1, -1};
bool has = false;
for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
if (l & 1) { res = has ? mergeN(res, st[l]) : st[l]; has = true; l++; }
if (r & 1) { --r; res = has ? mergeN(res, st[r]) : st[r]; has = true; }
}
return res;
}
// thoi gian nho nhat: chon ap x tren duong a - b sao cho max(dist(a,x), dist(x,b)) nho nhat
ll center(int a, int b, ll D) {
if (D == 0) return 0;
int c = lca(a, b);
ll da = wd[a] - wd[c];
if (2 * da < D) { swap(a, b); da = D - da; } // diem giua nam tren nhanh a -> c
int u = a;
for (int k = LOG - 1; k >= 0; k--) {
int x = up[k][u];
if (dep[x] >= dep[c] && 2 * (wd[a] - wd[x]) <= D) u = x;
}
ll du = wd[a] - wd[u]; // 2*du <= D
ll res = D - du;
if (u != c) res = min(res, wd[a] - wd[par[u]]); // ap ke tiep, da vuot qua diem giua
return res;
}
int main() {
scanf("%d %d %d", &n, &m, &q);
g.assign(n + 1, {});
for (int i = 0; i < n - 1; i++) {
int u, v, w; scanf("%d %d %d", &u, &v, &w);
g[u].push_back({v, w}); g[v].push_back({u, w});
}
par.assign(n + 1, 0); dep.assign(n + 1, 0); tin.assign(n + 1, 0); wd.assign(n + 1, 0);
ord_.clear();
// DFS khong de quy tu goc 1
vector<int> stk = {1}; par[1] = 1;
vector<char> vis(n + 1, 0);
while (!stk.empty()) {
int u = stk.back(); stk.pop_back();
vis[u] = 1; tin[u] = ord_.size(); ord_.push_back(u);
for (auto [v, w] : g[u]) if (!vis[v]) { par[v] = u; dep[v] = dep[u] + 1; wd[v] = wd[u] + w; stk.push_back(v); }
}
lg.assign(n + 2, 0);
for (int i = 2; i <= n + 1; i++) lg[i] = lg[i / 2] + 1;
sp.assign(lg[n] + 1, vector<int>(n));
for (int i = 0; i < n; i++) sp[0][i] = tin[par[ord_[i]]];
for (int k = 1; (1 << k) <= n; k++)
for (int i = 0; i + (1 << k) <= n; i++) sp[k][i] = min(sp[k - 1][i], sp[k - 1][i + (1 << (k - 1))]);
up.assign(LOG, vector<int>(n + 1));
for (int v = 1; v <= n; v++) up[0][v] = par[v];
for (int k = 1; k < LOG; k++)
for (int v = 1; v <= n; v++) up[k][v] = up[k - 1][up[k - 1][v]];
sz = 1; while (sz < m) sz <<= 1;
st.assign(2 * sz, {1, 1, 0});
for (int j = 0; j < m; j++) { int p; scanf("%d", &p); st[sz + j] = {p, p, 0}; }
for (int i = sz - 1; i >= 1; i--) st[i] = mergeN(st[2 * i], st[2 * i + 1]);
string out;
while (q--) {
int t, x, y; scanf("%d %d %d", &t, &x, &y);
if (t == 1) upd(x - 1, y);
else {
Node r = query(x - 1, y);
out += to_string(center(r.a, r.b, r.d)); out += '\n';
}
}
fputs(out.c_str(), stdout);
return 0;
}import sys
def far(s, n, start, adj, adw):
# DFS khong de quy tu ap s: tra ve ap xa s nhat, khoang cach va cha (dung de tim tam cay)
dd = [-1] * (n + 1); pp = [0] * (n + 1); dd[s] = 0; st = [s]
while st:
u = st.pop()
for e in range(start[u], start[u + 1]):
v = adj[e]
if dd[v] < 0:
dd[v] = dd[u] + adw[e]; pp[v] = u; st.append(v)
best = s
for v in range(1, n + 1):
if dd[v] > dd[best]:
best = v
return best, dd, pp
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]; m = data[1]; q = data[2]
p = 3
# danh sach ke dang mang phang (CSR)
deg = [0] * (n + 2)
for i in range(p, p + 3 * (n - 1), 3):
deg[data[i]] += 1; deg[data[i + 1]] += 1
start = [0] * (n + 2)
for v in range(1, n + 1):
start[v + 1] = start[v] + deg[v]
pos = start[:]
adj = [0] * (2 * n); adw = [0] * (2 * n)
for i in range(p, p + 3 * (n - 1), 3):
u = data[i]; v = data[i + 1]; w = data[i + 2]
adj[pos[u]] = v; adw[pos[u]] = w; pos[u] += 1
adj[pos[v]] = u; adw[pos[v]] = w; pos[v] += 1
p += 3 * (n - 1)
del pos, deg
# Chon goc la "tam" cua ca cay (ap giua duong kinh cua cay) de wd[u] + wd[v] la can tren
# tot cua d(u, v): khi ghep, cap nao co wd[u] + wd[v] <= ket qua hien tai thi bo qua, khoi tim lca.
A, _, _ = far(1, n, start, adj, adw)
B, dA, pA = far(A, n, start, adj, adw)
DT = dA[B]; rt = B; x = B
while x != A: # di tu B ve A, lay ap lam max(dA, DT - dA) nho nhat
if max(dA[x], DT - dA[x]) < max(dA[rt], DT - dA[rt]):
rt = x
x = pA[x]
del dA, pA
# DFS khong de quy tu goc rt: par, wd (tong thoi gian tu goc), tin (thu tu tham)
par = [0] * (n + 1); wd = [0] * (n + 1); tin = [0] * (n + 1)
order = []
vis = [False] * (n + 1)
par[rt] = rt
stk = [rt]
while stk:
u = stk.pop()
vis[u] = True
tin[u] = len(order); order.append(u)
wu = wd[u]
for e in range(start[u], start[u + 1]):
v = adj[e]
if not vis[v]:
par[v] = u; wd[v] = wu + adw[e]
stk.append(v)
del adj, adw, start, vis
# DANH SO LAI cac ap theo thu tu tham: ap u thanh tin[u]. Tu day moi mang deu theo so moi,
# nen "thu tu tham" cua ap u chinh la u (bot mot lan tra mang va truy cap bo nho gon hon).
W = [0] * n; P = [0] * n
for i in range(n):
u = order[i]; W[i] = wd[u]; P[i] = tin[par[u]]
wd = W; par = P
del W, P, order
# bang thua PHANG: sp[k*n + i] = min wd[cha] cua cac ap so i .. i + 2^k - 1.
# Voi u < v: min tren doan (u, v] chinh la wd[lca(u, v)]
# (moi ap trong doan deu thuoc cay con cua lca, va co mot ap la con cua lca).
row = [wd[par[i]] for i in range(n)]
sp = row[:]
k = 1
while (1 << k) <= n:
h = 1 << (k - 1)
row = [x if x < y else y for x, y in zip(row, row[h:])]
row.extend([0] * (n - len(row)))
sp.extend(row)
k += 1
# doan (lo, hi] do dai L = hi - lo: min = min(sp[F1[L] + lo], sp[F2[L] + hi])
F1 = [0] * (n + 1); F2 = [0] * (n + 1)
k = 0
for L in range(1, n + 1):
if (2 << k) <= L:
k += 1
F1[L] = k * n + 1; F2[L] = k * n - (1 << k) + 1
del row
# nhay nhi phan PHANG: up[k*(n+1) + v] = to tien thu 2^k cua v
LOG = max(1, n.bit_length())
N1 = n
up = par[:]
for k in range(1, LOG):
b = (k - 1) * N1
up.extend([up[b + up[b + v]] for v in range(N1)])
# segment tree tren day hoc tro: nut i luu cap xa nhat (SA[i], SB[i]), SD[i] = khoang cach
sz = 1
while sz < m:
sz <<= 1
SA = [0] * (2 * sz); SB = [0] * (2 * sz); SD = [0] * (2 * sz) # la dem: ap so 0 (goc), khong bao gio duoc truy van
home = [tin[x] for x in data[p:p + m]]
SA[sz:sz + m] = home; SB[sz:sz + m] = home
del home
p += m
todo = range(sz - 1, 0, -1) # lan dau: dung ca cay; ve sau: cac nut tren duong len goc
out = []
for ev in range(q + 1):
# ---- tinh lai cac nut trong todo tu hai con (ghep duong kinh) ----
for i in todo:
l = 2 * i; r = l + 1
a1 = SA[l]; b1 = SB[l]; a2 = SA[r]; b2 = SB[r]
if SD[r] > SD[l]:
ra = a2; rb = b2; rd = SD[r]
else:
ra = a1; rb = b1; rd = SD[l]
u = a1
while True: # u lan luot la a1, b1 (bo qua neu trung)
wu = wd[u]
v = a2
while True: # v lan luot la a2, b2
if u != v and wu + wd[v] > rd: # d(u, v) <= wd[u] + wd[v]: khong hon rd thi bo qua
if u < v:
L = v - u; s1 = sp[F1[L] + u]; s2 = sp[F2[L] + v]
else:
L = u - v; s1 = sp[F1[L] + v]; s2 = sp[F2[L] + u]
d = wu + wd[v] - 2 * (s1 if s1 < s2 else s2)
if d > rd:
ra = u; rb = v; rd = d
if v == b2:
break
v = b2
if u == b1:
break
u = b1
if ev and rd == SD[i] and ra == SA[i] and rb == SB[i]:
break # nut khong doi thi cac nut to tien cung khong doi: dung som
SA[i] = ra; SB[i] = rb; SD[i] = rd
if ev == q:
break
t = data[p]; x = data[p + 1]; y = data[p + 2]; p += 3
if t == 1:
i = sz + x - 1
y = tin[y]
SA[i] = y; SB[i] = y; SD[i] = 0
todo = []
i >>= 1
while i:
todo.append(i); i >>= 1
continue
todo = ()
# ---- truy van: ghep lan luot cac nut phu doan [x, y] vao (a, b, D) ----
l = x - 1 + sz; r = y + sz
a = -1; b = -1; D = -1
while l < r:
j = -1
if l & 1:
j = l; l += 1
elif r & 1:
r -= 1; j = r
if j < 0:
l >>= 1; r >>= 1
continue
if a < 0:
a = SA[j]; b = SB[j]; D = SD[j]
continue
a2 = SA[j]; b2 = SB[j]; ra = a; rb = b
if SD[j] > D:
ra = a2; rb = b2; D = SD[j]
u = a
while True:
wu = wd[u]
v = a2
while True:
if u != v and wu + wd[v] > D:
if u < v:
L = v - u; s1 = sp[F1[L] + u]; s2 = sp[F2[L] + v]
else:
L = u - v; s1 = sp[F1[L] + v]; s2 = sp[F2[L] + u]
d = wu + wd[v] - 2 * (s1 if s1 < s2 else s2)
if d > D:
ra = u; rb = v; D = d
if v == b2:
break
v = b2
if u == b:
break
u = b
a = ra; b = rb
if D == 0:
out.append("0")
continue
# wc = wd[lca(a, b)]; neu nhanh a -> lca ngan hon D/2 thi doi vai a, b
if a < b:
L = b - a; s1 = sp[F1[L] + a]; s2 = sp[F2[L] + b]
else:
L = a - b; s1 = sp[F1[L] + b]; s2 = sp[F2[L] + a]
wc = s1 if s1 < s2 else s2
if 2 * (wd[a] - wc) < D:
a = b
# nhay nhi phan tu a len to tien cao nhat u con thoa: khong vuot qua lca (wd[u] >= wc)
# va chua qua diem giua (2*(wd[a] - wd[u]) <= D), tuc 2*wd[u] >= lim
wa = wd[a]
lim = 2 * wa - D
if 2 * wc > lim:
lim = 2 * wc
u = a
for k in range(LOG - 1, -1, -1):
xx = up[k * N1 + u]
if 2 * wd[xx] >= lim:
u = xx
res = D - (wa - wd[u])
if wd[u] != wc: # u chua phai lca: thu them ap cha (da qua diem giua)
alt = wa - wd[par[u]]
if alt < res:
res = alt
out.append(str(res))
sys.stdout.write("\n".join(out) + ("\n" if out else ""))
main()Không gian$O(N \log N + M)$
Thời gian$O(N \log N + (M + Q) \log M + Q \log N)$
Vì sao phải xét cả hai ấp kẹp điểm giữa?
Ấp $u$ chưa qua điểm giữa thì em ở $b$ là em tới sau cùng; ấp cha của $u$ đã qua điểm giữa thì em ở $a$ tới sau cùng. Không biết trước bên nào "lệch" ít hơn, nên phải so cả hai. Quên ấp thứ hai là một lỗi rất hay gặp (xem bảng chấm cuối bài).Chạy tay lời giải chuẩn trên dữ liệu nhỏ (tối đa 10 ấp, 8 học trò, 6 sự kiện). Để gọn, các lần gọi lca/dist bên trong mergeN được tính luôn trong một bước:
C++▶ Chạy tay từng dòng codeDFS không đệ quy, bảng thưa LCA, nhảy nhị phân, segment tree ghép đường kính.
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4
5const int LOG = 17;
6int n, m, q;
7vector<vector<pair<int, int>>> g;
8vector<int> par, dep, tin, ord_, lg;
9vector<ll> wd; // wd[v] = tong trong so tu goc toi v
10vector<vector<int>> sp, up; // sp: bang thua cho LCA, up: nhay nhi phan
11
12int lca(int u, int v) {
13 if (u == v) return u;
14 int l = tin[u], r = tin[v];
15 if (l > r) swap(l, r);
16 l++; // min tin[cha] tren doan (l, r] la tin[lca]
17 int k = lg[r - l + 1];
18 return ord_[min(sp[k][l], sp[k][r - (1 << k) + 1])];
19}
20ll dist(int u, int v) { return wd[u] + wd[v] - 2 * wd[lca(u, v)]; }
21
22struct Node { int a, b; ll d; }; // cap xa nhat (a, b) cua tap, d = dist(a, b)
23Node mergeN(const Node& x, const Node& y) {
24 Node r = x.d >= y.d ? x : y;
25 int P[2] = {x.a, x.b}, Qv[2] = {y.a, y.b};
26 for (int i = 0; i < 2; i++)
27 for (int j = 0; j < 2; j++) {
28 ll d = dist(P[i], Qv[j]);
29 if (d > r.d) r = {P[i], Qv[j], d};
30 }
31 return r;
32}
33
34vector<Node> st;
35int sz;
36void upd(int pos, int v) {
37 pos += sz; st[pos] = {v, v, 0};
38 for (pos >>= 1; pos >= 1; pos >>= 1) st[pos] = mergeN(st[2 * pos], st[2 * pos + 1]);
39}
40Node query(int l, int r) { // [l, r) chi so tu 0
41 Node res = {-1, -1, -1};
42 bool has = false;
43 for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
44 if (l & 1) { res = has ? mergeN(res, st[l]) : st[l]; has = true; l++; }
45 if (r & 1) { --r; res = has ? mergeN(res, st[r]) : st[r]; has = true; }
46 }
47 return res;
48}
49
50// thoi gian nho nhat: chon ap x tren duong a - b sao cho max(dist(a,x), dist(x,b)) nho nhat
51ll center(int a, int b, ll D) {
52 if (D == 0) return 0;
53 int c = lca(a, b);
54 ll da = wd[a] - wd[c];
55 if (2 * da < D) { swap(a, b); da = D - da; } // diem giua nam tren nhanh a -> c
56 int u = a;
57 for (int k = LOG - 1; k >= 0; k--) {
58 int x = up[k][u];
59 if (dep[x] >= dep[c] && 2 * (wd[a] - wd[x]) <= D) u = x;
60 }
61 ll du = wd[a] - wd[u]; // 2*du <= D
62 ll res = D - du;
63 if (u != c) res = min(res, wd[a] - wd[par[u]]); // ap ke tiep, da vuot qua diem giua
64 return res;
65}
66
67int main() {
68 scanf("%d %d %d", &n, &m, &q);
69 g.assign(n + 1, {});
70 for (int i = 0; i < n - 1; i++) {
71 int u, v, w; scanf("%d %d %d", &u, &v, &w);
72 g[u].push_back({v, w}); g[v].push_back({u, w});
73 }
74 par.assign(n + 1, 0); dep.assign(n + 1, 0); tin.assign(n + 1, 0); wd.assign(n + 1, 0);
75 ord_.clear();
76 // DFS khong de quy tu goc 1
77 vector<int> stk = {1}; par[1] = 1;
78 vector<char> vis(n + 1, 0);
79 while (!stk.empty()) {
80 int u = stk.back(); stk.pop_back();
81 vis[u] = 1; tin[u] = ord_.size(); ord_.push_back(u);
82 for (auto [v, w] : g[u]) if (!vis[v]) { par[v] = u; dep[v] = dep[u] + 1; wd[v] = wd[u] + w; stk.push_back(v); }
83 }
84 lg.assign(n + 2, 0);
85 for (int i = 2; i <= n + 1; i++) lg[i] = lg[i / 2] + 1;
86 sp.assign(lg[n] + 1, vector<int>(n));
87 for (int i = 0; i < n; i++) sp[0][i] = tin[par[ord_[i]]];
88 for (int k = 1; (1 << k) <= n; k++)
89 for (int i = 0; i + (1 << k) <= n; i++) sp[k][i] = min(sp[k - 1][i], sp[k - 1][i + (1 << (k - 1))]);
90 up.assign(LOG, vector<int>(n + 1));
91 for (int v = 1; v <= n; v++) up[0][v] = par[v];
92 for (int k = 1; k < LOG; k++)
93 for (int v = 1; v <= n; v++) up[k][v] = up[k - 1][up[k - 1][v]];
94 sz = 1; while (sz < m) sz <<= 1;
95 st.assign(2 * sz, {1, 1, 0});
96 for (int j = 0; j < m; j++) { int p; scanf("%d", &p); st[sz + j] = {p, p, 0}; }
97 for (int i = sz - 1; i >= 1; i--) st[i] = mergeN(st[2 * i], st[2 * i + 1]);
98 string out;
99 while (q--) {
100 int t, x, y; scanf("%d %d %d", &t, &x, &y);
101 if (t == 1) upd(x - 1, y);
102 else {
103 Node r = query(x - 1, y);
104 out += to_string(center(r.a, r.b, r.d)); out += '\n';
105 }
106 }
107 fputs(out.c_str(), stdout);
108 return 0;
109}
Bộ test chấm "bắt" những lỗi nào?
| Cách làm | Sub 1 | Sub 2 | Sub 3 | Sub 4 | Sub 5 | Điểm |
|---|---|---|---|---|---|---|
| Cách 1 – thử mọi ấp làm điểm hẹn | Đúng | TLE | TLE | TLE | TLE | 10 |
| Cách 2 – hai lần đo xa mỗi buổi | Đúng | Đúng | TLE | TLE | TLE | 25 |
| Cách 3 – đường thẳng: min/max (cây khác: Cách 2) | Đúng | Đúng | Đúng | TLE | TLE | 40 |
| Cách 4 – w = 1: segment tree đường kính, ⌈D/2⌉ (còn lại: Cách 2) | Đúng | Đúng | TLE | Đúng | TLE | 50 |
| Cách 5 – thêm nhảy nhị phân tìm điểm giữa (lời giải chuẩn) | Đúng | Đúng | Đúng | Đúng | Đúng | 100 |
| Sai: luôn in $\lceil D/2 \rceil$ (tưởng luôn có ấp ở giữa) | 2/7 | 0/7 | 0/6 | Đúng | 0/8 | 27,9 |
| Sai: chỉ xét ấp $u$, quên ấp cha đã qua điểm giữa | 2/7 | 0/7 | 1/6 | Đúng | 0/8 | 30,4 |
Sai: lưu thời gian $wd$ bằng int | 3/7 | 1/7 | 1/6 | Đúng | 1/8 | 38,3 |
| Sai: ghép đường kính chỉ thử 4 cặp chéo, quên hai đường kính cũ | 3/7 | 0/7 | 1/6 | 0/6 | 0/8 | 6,8 |
| Sai: chỉ chọn điểm hẹn là nhà một em (trên nền Cách 2) | 2/7 | 0/7 | TLE | TLE | TLE | 2,9 |
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: 34 test (subtask 1: 7 test, subtask 2: 7 test, subtask 3: 6 test, subtask 4: 6 test, subtask 5: 8 test), chấm kiểu "đúng test nào được điểm test đó". Mọi test subtask 2 có $N = M = Q = 3000$; mọi test subtask 3–5 có $N = M = Q = 10^5$ nên làm lại từ đầu cho từng buổi (Cách 2) chắc chắn quá giờ. Cây trong bộ test có đủ hình dạng: ngẫu nhiên, gần như một đường dài (độ sâu cỡ $10^5$ — ai DFS đệ quy coi chừng tràn ngăn xếp), hình sao, cây nhị phân, "chổi", nhiều nhánh dài; nhà các em thường ở các ấp lá để điểm giữa rơi vào ấp không có ai ở; thời gian $w_i$ lên tới $10^9$ nên khoảng cách vượt xa giới hạn int. Lời giải chuẩn chạy tối đa khoảng 0,3 giây. Bản Python nên nộp bằng PyPy 3 (giới hạn 5 giây).
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
Tự học thuật toán: khó ở đâu?
Đọc xong một bài giải là bước đầu. Phần lớn học sinh tự học sẽ gặp những trở ngại sau:
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
Học cùng thầy Nam Sơn, các trở ngại đó được gỡ bỏ:
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét