# Kỹ thuật Tree Rerooting (Dời gốc cây)
## I. Đặt vấn đề
Cho cây có $n$ nút, nhiệm vụ là tính giá trị $F[i]$ ứng với mỗi nút $i$ dưới quan điểm nút đó là gốc của cây.
Ví dụ, $F[i]$ có thể là:
* Tổng khoảng cách từ nút $i$ đến tất cả nút khác.
* Số nút con của nút $i$.
Link bài tập: https://tritrang.dev/problem/cses1133
### Phương pháp duyệt toàn bộ gốc
1. Với mỗi $i$ từ 1 đến $n$:
1. Đặt gốc cây tại $i$.
2. Duyệt cây (DFS/BFS) để tính $F[i]$.
2. Chọn kết quả tối ưu (ví dụ, giá trị lớn nhất hoặc nhỏ nhất).
Thời gian: $O(n)$ cho mỗi gốc, tổng $O(n^2)$. Với $n$ lớn (ví dụ $10^5$), cách này không khả thi.
## II. Ý tưởng Tree Rerooting
Thay vì duyệt lại toàn bộ cây cho mỗi gốc mới, ta chỉ duyệt một lần khi gốc là một nút cố định (ví dụ $1$).
* **Bước 1**: Duyệt DFS từ gốc ban đầu để tính trước mọi giá trị phụ trợ (ví dụ: số nút con, tổng khoảng cách từ gốc gốc). Gọi kết quả này là `F_root[u]`.
* **Bước 2**: Sử dụng đệ quy đưa gốc từ nút hiện tại $u$ sang nút con $v$ (kỹ thuật *rerooting*), cập nhật giá trị $F[v]$ trong $O(1)$ dựa vào $F[u]$ và các thông tin phụ trợ.
* Khi đổi gốc từ $u$ sang $v$:
1. Loại bỏ đóng góp của nhánh $v$ từ $u$.
2. Thêm đóng góp của phần cây còn lại (các nút ngoài nhánh $v$) vào $v$.
3. Cập nhật các thông tin phụ trợ khác nếu cần.
* **Bước 3**: Quay lại gốc $u$ và tiếp tục với các nút con khác.
Nhờ vậy, ta chỉ duyệt các cạnh của cây đúng một lần, tổng thời gian $O(n)$.
## III. Mô hình tổng quát (Pseudocode)
### 1. Hàm DFS khởi tạo
```cpp
void dfs_init(int u, int parent) {
// Khởi tạo thông tin cho nút u
size[u] = 1; // ví dụ: số nút con (bao gồm u)
sumDist[u] = 0; // ví dụ: tổng khoảng cách từ gốc ban đầu
for (int v : adj[u]) if (v != parent) {
dfs_init(v, u);
size[u] += size[v];
sumDist[u] += sumDist[v] + size[v];
}
}
```
### 2. Hàm Rerooting
```cpp
void reroot(int u, int parent) {
// Khi gốc chuyển từ parent -> u, ta đã có F[parent] và cần tính F[u]
// Lưu lại giá trị ban đầu
int prev_u = sumDist[u];
int prev_parent = sumDist[parent];
int size_u = size[u];
int size_parent = size[parent];
// Bước 1: loại bỏ đóng góp của u ra khỏi parent
sumDist[parent] -= (sumDist[u] + size[u]);
size[parent] -= size[u];
// Bước 2: thêm đóng góp của phần cây còn lại vào u
sumDist[u] += (sumDist[parent] + size[parent]);
size[u] += size[parent];
// Lưu kết quả F[u]
F[u] = sumDist[u];
// Đệ quy cho con của u
for (int v : adj[u]) if (v != parent) {
reroot(v, u);
}
// Khôi phục lại trạng thái ban đầu
sumDist[u] = prev_u;
sumDist[parent] = prev_parent;
size[u] = size_u;
size[parent] = size_parent;
}
```
### 3. Hàm chính
```cpp
void solve() {
// 1. DFS khởi tạo từ gốc 1
dfs_init(1, 0);
F[1] = sumDist[1];
// 2. Reroot để tính F[i] cho mọi i
for (int v : adj[1]) {
reroot(v, 1);
}
// 3. Xuất kết quả (ví dụ lấy max hoặc min)
int answer = *max_element(F + 1, F + n + 1);
cout << answer;
}
```
## IV. Phân tích độ phức tạp
* **Khởi tạo (dfs\_init)**: duyệt cây một lần → $O(n)$.
* **Rerooting (reroot)**: mỗi cạnh được xử lý hai lần (đi và về) → $O(n)$.
**Tổng**: $O(n)$.
---
> **Chú ý**: Tuỳ bài toán cụ thể, ta có thể lưu các tham số phụ trợ khác (như tổng lũy thừa, trọng số cạnh, …) và cập nhật tương tự trong bước rerooting.
## Mã nguồn C++ đầy đủ
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
void file(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#define task ""
if(fopen(task".in", "r")) {
freopen(task".in", "r", stdin);
freopen(task".out", "w", stdout);
}
}
const int N = 1000001;
int n, sumDist[N], sz[N], F[N];
vector<int> adj[N];
void dfs_init(int u, int parent) {
// Khởi tạo thông tin cho nút u
sz[u] = 1; // ví dụ: số nút con (bao gồm u)
sumDist[u] = 0; // ví dụ: tổng khoảng cách từ gốc ban đầu
for (int v : adj[u]) if (v != parent) {
dfs_init(v, u);
sz[u] += sz[v];
sumDist[u] += sumDist[v] + sz[v];
}
}
void reroot(int u, int parent) {
// Khi gốc chuyển từ parent -> u, ta đã có F[parent] và cần tính F[u]
// Lưu lại giá trị ban đầu
int prev_u = sumDist[u];
int prev_parent = sumDist[parent];
int size_u = sz[u];
int size_parent = sz[parent];
// Bước 1: loại bỏ đóng góp của u ra khỏi parent
sumDist[parent] -= (sumDist[u] + sz[u]);
sz[parent] -= sz[u];
// Bước 2: thêm đóng góp của phần cây còn lại vào u
sumDist[u] += (sumDist[parent] + sz[parent]);
sz[u] += sz[parent];
// Lưu kết quả F[u]
F[u] = sumDist[u];
// Đệ quy cho con của u
for (int v : adj[u]) if (v != parent) reroot(v, u);
// Khôi phục lại trạng thái ban đầu
sumDist[u] = prev_u;
sumDist[parent] = prev_parent;
sz[u] = size_u;
sz[parent] = size_parent;
}
void solve() {
// 1. DFS khởi tạo từ gốc 1
dfs_init(1, 0);
F[1] = sumDist[1];
// 2. Reroot để tính F[i] cho mọi i
for (int v : adj[1]) reroot(v, 1);
for (int i=1; i<=n; i++) cout << F[i] << " ";
}
int32_t main() {
file();
cin >> n;
for (int i=1; i<n; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
solve();
return 0;
}
```
---
# Hướng dẫn giải bài "Cây với chi phí lớn nhất"
## 1. Tóm tắt đề bài
Cho một cây gồm $n$ đỉnh, mỗi đỉnh $i$ có giá trị $a_i$. Với mỗi đỉnh **v** được chọn làm gốc, định nghĩa **cost(v)** = $\sum_{i=1}^{n} \mathrm{dist}(i, v) \times a_i$, trong đó **dist(i, v)** là khoảng cách (số cạnh) trên đường đi đơn giữa **i** và **v**. Yêu cầu tìm giá trị lớn nhất của **cost(v)** khi ta có thể chọn **v** tuỳ ý.
Link bài tập: https://tritrang.dev/problem/cf1092f
## 2. Phân tích và quan sát
* Tính trực tiếp $\mathrm{cost}(v)$ cho mỗi **v** bằng DFS/BFS từ **v** sẽ tốn **O(n)** cho mỗi đỉnh, tổng **O(n^2)**, không chấp nhận với **n** lên tới $2 \times 10^5$.
* Sử dụng kỹ thuật **Tree DP + Rerooting** để tính hiệu quả trong **O(n)**:
1. Chọn một đỉnh gốc ban đầu (ví dụ **1**), tính hai giá trị sau bằng một DFS:
* **subSum\[u]** = tổng giá trị **a<sub>i</sub>** của toàn bộ các đỉnh trong cây con gốc tại **u**.
* **dp\[1]** = giá trị **cost(1)** = $\sum_{i=1}^{n} \mathrm{depth}(i) \times a_i$ (với độ sâu tính từ gốc **1**).
2. Sau khi đã có **subSum** và **dp\[1]**, duyệt lại cây theo DFS thứ hai để tính **dp\[v]** cho mọi đỉnh **v** bằng công thức chuyển trạng thái (rerooting):
$$
\mathrm{cost}(v) = \mathrm{cost}(u) + \bigl(\mathrm{TotalSumA} - 2 \times \mathrm{subSum}[v]\bigr)
$$
Trong đó:
* **u** là cha của **v** trong DFS rerooting.
* **TotalSumA** = $\sum_{i=1}^{n} a_i$.
* Khi đổi gốc từ **u** sang **v**, khoảng cách tất cả đỉnh trong cây con **v** giảm 1, khoảng cách đỉnh ngoài cây con **v** tăng 1.
3. Trong quá trình DFS rerooting, cập nhật kết quả lớn nhất **ans** = max(**ans**, **cost(v)**).
## 3. Các bước triển khai
1. **Đọc dữ liệu**: số đỉnh **n**, mảng **a** kích thước **n**, và **n-1** cạnh.
2. **Xây dựng** danh sách kề của cây.
3. **DFS1 (tính subSum và dp\[1])** từ gốc 1:
* `subSum[u] = a[u] + sum(subSum[child])`
* Đồng thời tích luỹ `dp1 += depth * a[u]`.
4. Tính `TotalSumA = sum(a[i])`.
5. **DFS2 (rerooting)** từ gốc 1 lên toàn cây:
* Với cạnh `u -> v`, tính:
```
dp[v] = dp[u] + (TotalSumA - 2 * subSum[v]);
```
* Cập nhật `ans = max(ans, dp[v])`.
6. **In** ra `ans`.
## 4. Độ phức tạp
* Xây cây và đọc dữ liệu: **O(n)**
* DFS1: **O(n)**
* DFS2 (rerooting): **O(n)**
Tổng: **O(n)**, phù hợp với $n \le 2 \times 10^5$.
## 5. Mã nguồn C++ đầy đủ
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
vector<ll> a, subSum, dp;
vector<vector<int>> adj;
ll TotalSumA = 0;
ll ans = LLONG_MIN;
// Tính subSum[u] và dp[1] = cost khi gốc là 1
ll dp1 = 0;
void dfs1(int u, int p, int depth) {
subSum[u] = a[u];
dp1 += (ll)depth * a[u];
for (int v : adj[u]) {
if (v == p) continue;
dfs1(v, u, depth + 1);
subSum[u] += subSum[v];
}
}
// Reroot từ u sang các con v
void dfs2(int u, int p) {
ans = max(ans, dp[u]);
for (int v : adj[u]) {
if (v == p) continue;
// cost khi gốc chuyển từ u sang v
dp[v] = dp[u] + (TotalSumA - 2 * subSum[v]);
dfs2(v, u);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.assign(n + 1, 0);
subSum.assign(n + 1, 0);
dp.assign(n + 1, 0);
adj.assign(n + 1, {});
for (int i = 1; i <= n; i++) {
cin >> a[i];
TotalSumA += a[i];
}
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// DFS đầu tiên từ gốc 1
dfs1(1, 0, 0);
dp[1] = dp1;
// Reroot để tính dp[v] cho mọi v
dfs2(1, 0);
cout << ans;
return 0;
}
```
---
# Hướng dẫn giải bài "Cây con màu trắng lớn nhất"
## 1. Tóm tắt đề
Cho một cây vô hướng có $n$ đỉnh $(1 \le n \le 2 \times 10^5)$. Mỗi đỉnh **i** được tô màu trắng nếu $a_i = 1$, hoặc đen nếu $a_i = 0$. Với mỗi đỉnh $v$, ta cần chọn một cây con (subtree)(connected subgraph chứa v) sao cho hiệu số **(số trắng) − (số đen)** đạt giá trị lớn nhất. In ra **res\_v** cho mọi đỉnh $v$.
Link nộp bài: https://tritrang.dev/problem/cf1324f
## 2. Chuyển đổi trọng số
* Gán mỗi đỉnh một **trọng số**:
$$
w_i = \begin{cases}
+1, & a_i = 1 \quad(\text{trắng})\\
-1, & a_i = 0 \quad(\text{đen})
\end{cases}
$$
* Bài toán trở thành: với mỗi đỉnh v, tìm giá trị lớn nhất của tổng trọng số của một cây con liên thông chứa v.
## 3. DP trên cây (post-order)
Chọn gốc tạm thời ở đỉnh 1. Định nghĩa:
> **dp1\[v]** = tổng trọng số tối đa của một cây con liên thông nằm **trong** cây con (subtree) tại v và **chứa** v.
Công thức tính:
```text
dp1[v] = w_v
for mỗi u con của v:
nếu dp1[u] > 0 thì dp1[v] += dp1[u]
```
Lí do: nếu dp1\[u] ≤ 0, việc thêm toàn bộ cây con tại u chỉ làm giảm tổng.
## 4. Rerooting (DP 2 lượt)
Để mở rộng kết quả ra toàn cây (không chỉ subtree gốc 1), ta dùng kỹ thuật **rerooting**:
1. Tính **dp1\[]** bằng DFS1 từ gốc 1.
2. Khởi tạo **dp2\[1] = dp1\[1]**.
3. Dùng DFS2 để đẩy kết quả từ v xuống mỗi con u:
* Giả sử đang ở v với dp2\[v] đã biết.
* Khi chuyển gốc từ v sang u, phần đóng góp từ u đã được tính trong dp1\[v]:
$\delta = \max(0, dp1[u])$.
* Phần còn lại (bao gồm v và các nhánh khác ngoài u) có tổng:
$\Delta = dp2[v] - \delta$.
* Tính dp2\[u] = dp1\[u] + max(0, Δ).
Pseudocode:
```cpp
void dfs1(int v, int p) {
dp1[v] = w[v];
for(int u: adj[v]) if(u!=p) {
dfs1(u, v);
if(dp1[u] > 0) dp1[v] += dp1[u];
}
}
void dfs2(int v, int p) {
// dp2[v] đã sẵn sàng
result[v] = dp2[v];
for(int u: adj[v]) if(u!=p) {
ll keep = max(0LL, dp1[u]);
ll rest = dp2[v] - keep;
dp2[u] = dp1[u] + max(0LL, rest);
dfs2(u, v);
}
}
// Trong main:
dfs1(1, 0);
dp2[1] = dp1[1];
dfs2(1, 0);
// result[i] chứa đáp án cho đỉnh i
```
## 5. Kết xuất kết quả
* In ra **res<sub>1</sub>, res<sub>2</sub>, …, res<sub>n</sub>** cách nhau bởi dấu cách.
## 6. Độ phức tạp
* Xây danh sách kề và đọc vào: **O(n)**
* DFS1 + DFS2: mỗi cạnh được duyệt 2 lần, tổng **O(n)**
* Phù hợp với n **≤ 2·10^5**.
---
> **Chú ý:** Sử dụng kiểu số đủ lớn (64-bit) để tránh tràn khi cộng trừ nhiều.
## Mã nguồn C++ đầy đủ
```cpp
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> col;
vector<vector<int>> g;
vector<int> dp, ans;
// DFS đầu tiên: tính dp[u] = hiệu số tối đa (số đỉnh trắng - số đỉnh đen) trong cây con có gốc u
void dfs1(int u, int p) {
dp[u] = col[u];
for (int v : g[u]) {
if (v == p) continue;
dfs1(v, u);
dp[u] += max(0, dp[v]);
}
}
// DFS thứ hai (reroot): tính ans[v] dựa trên ans[u] và dp[v] khi dời gốc từ u sang v
void dfs2(int u, int p) {
for (int v : g[u]) {
if (v == p) continue;
// Loại bỏ đóng góp dp[v] khỏi ans[u], rồi cộng phần dư nếu còn dương
ans[v] = dp[v] + max(0, ans[u] - max(0, dp[v]));
dfs2(v, u);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
col.assign(n + 1, 0);
for (int i = 1; i <= n; i++) {
int a;
cin >> a;
// trắng = +1, đen = -1
col[i] = (a == 1 ? 1 : -1);
}
g.assign(n + 1, {});
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dp.assign(n + 1, 0);
ans.assign(n + 1, 0);
// Tính dp ban đầu cho gốc 1
dfs1(1, 0);
// Kết quả cho nút 1 (gốc ban đầu)
ans[1] = dp[1];
// Sử dụng reroot để tính ans cho tất cả nút
dfs2(1, 0);
// In kết quả
for (int i = 1; i <= n; i++) {
cout << ans[i] << (i == n ? '\n' : ' ');
}
return 0;
}
```
---
# Hướng dẫn giải bài "Cặp đỉnh có khoảng cách bằng k trong cây"
## Đề bài
Cho một cây vô hướng có **n** đỉnh (đánh số từ 1 đến n) và một số nguyên dương **k**. Hãy đếm số cặp đỉnh **(u, v)** sao cho khoảng cách (số cạnh trên đường đi ngắn nhất) giữa **u** và **v** bằng **k**. Với n ≤ 5·10⁴, k ≤ 500.
Link bài tập: https://tritrang.dev/problem/eolymp4104
## Kỹ thuật rerooting với hai bảng f1, f2
Thay vì chỉ dùng một mảng dp và rollback, ta duy trì hai bảng:
* **f1\[u]\[d]**: số đỉnh nằm trong subtree của u có khoảng cách **d** đến u.
* **f2\[u]\[d]**: số đỉnh trong toàn bộ cây có khoảng cách **d** đến u (bao gồm cả bên ngoài subtree).
### Bước 1: DFS1 tính f1
1. Khởi tạo `f1[u][0] = 1` (đỉnh u).
2. Với mỗi con v của u, đệ quy `dfs1(v, u)`, rồi gộp vào:
```cpp
for (int d = 1; d <= k; ++d) {
f1[u][d] += f1[v][d-1];
}
```
Sau `dfs1(1, 0)`, bảng **f1** đã đúng cho mọi u với subtree khi gốc = 1.
### Bước 2: Khởi tạo f2 tại gốc và DFS2 lan truyền
1. Tại gốc 1, toàn bộ cây = subtree, nên:
```cpp
for (int d = 0; d <= k; ++d)
f2[1][d] = f1[1][d];
```
2. Đệ quy `dfs2(u, p)`: với mỗi con v của u:
* `f2[v][0] = 1`.
* Với mỗi `d = 1..k`:
```cpp
int inSub = f1[v][d];
int outSub = f2[u][d-1] - (d-2 >= 0 ? f1[v][d-2] : 0);
f2[v][d] = inSub + outSub;
```
* Đệ quy tiếp `dfs2(v, u)`.
Giải thích **outSub**: số đỉnh ở khoảng cách `d-1` từ u trong toàn cây (f2\[u]\[d-1]) trừ đi số đỉnh ở khoảng cách `d-1` từ u nằm trong subtree v, tức `f1[v][d-2]`.
### Bước 3: Tính kết quả
Tổng số cặp đỉnh cách nhau đúng k là:
```cpp
long long total = 0;
for (int u = 1; u <= n; ++u)
total += f2[u][k];
// chia 2 vì đếm mỗi cặp hai lần
cout << (total / 2) << '\n';
```
## Mã nguồn C++ đầy đủ
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 50000 + 5;
int n, k;
vector<int> adj[MAXN];
vector<vector<int>> f1, f2;
void dfs1(int u, int p) {
f1[u][0] = 1;
for (int v : adj[u]) if (v != p) {
dfs1(v, u);
for (int d = 1; d <= k; ++d) {
f1[u][d] += f1[v][d-1];
}
}
}
void dfs2(int u, int p) {
for (int v : adj[u]) if (v != p) {
f2[v][0] = 1;
for (int d = 1; d <= k; ++d) {
int inSub = f1[v][d];
int outSub = f2[u][d-1] - ((d-2 >= 0) ? f1[v][d-2] : 0);
f2[v][d] = inSub + outSub;
}
dfs2(v, u);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
f1.assign(n+1, vector<int>(k+1, 0));
f2.assign(n+1, vector<int>(k+1, 0));
dfs1(1, 0);
// khởi tạo f2 tại gốc
for (int d = 0; d <= k; ++d) f2[1][d] = f1[1][d];
dfs2(1, 0);
ll total = 0;
for (int u = 1; u <= n; ++u)
total += f2[u][k];
cout << (total / 2) << '\n';
return 0;
}
```
---
# Hướng dẫn giải bài "Tô màu cây"
## 1. Đề bài
Cho một cây (đồ thị vô hướng, liên thông, không có chu trình) gồm $n$ đỉnh. Ban đầu tất cả các đỉnh đều có màu trắng. Trò chơi diễn ra như sau:
1. *Lượt đầu*: bạn chọn một đỉnh bất kỳ và sơn nó thành màu đen.
2. *Các lượt tiếp theo*: bạn chọn một đỉnh trắng kề (có cạnh nối) với **bất kỳ** đỉnh đen nào và sơn nó thành đen.
3. Mỗi lần chọn một đỉnh $u$, bạn được cộng điểm bằng kích thước của thành phần con chỉ gồm các đỉnh trắng chứa $u$ vào thời điểm đó.
4. Trò chơi kết thúc khi mọi đỉnh đều thành đen.
*Yêu cầu*: Tìm cách chơi sao cho tổng điểm thu được là **tối đa**.
Link bài tập: https://tritrang.dev/problem/cf1187e
## 2. Phân tích và ý tưởng
Quan sát rằng mỗi lần chọn đỉnh, ta “cắt” đi một thành phần con trắng; tổng điểm chính là tổng kích thước các thành phần con đó.
Nếu xét việc chọn thứ tự các đỉnh, ta thực chất là muốn tính tổng kích thước thành phần con trắng cho từng đỉnh khi nó được chuyển sang đen. Để tối ưu, ta cần tìm thứ tự sao cho tổng này lớn nhất. Tuy nhiên, do cây có cấu trúc đặc biệt, bài toán tối ưu chính là: chọn gốc sao cho tổng chuỗi kích thước các cây con (subtree sizes) được cộng tối đa.
Đây chính là bài toán **Rerooting DP** trên cây:
* Đầu tiên ta tạm chọn nút $1$ làm gốc, tính kích thước mỗi cây con:
$\text{siz}[u] = \text{số đỉnh trong cây con của }u$
* Khi gốc tạm là 1, điểm ban đầu
$$
dp[1] = \sum_{u=1}^{n} \text{siz}[u]
$$
chính là tổng sizes của mọi đỉnh.
* Sử dụng rerooting, giả sử đã biết $dp[u]$ với cây gốc là $u$. Khi chuyển gốc từ $u$ sang con $v$, ta có:
$$
dp[v] = dp[u] - \text{siz}[v] + (n - \text{siz}[v]).
$$
Giải thích:
* Khi đổi gốc, thành phần con của $v$ (khi gốc là $u$) với độ lớn siz\[v] giờ sẽ trở thành phần *ngoài* gốc có kích thước $n - siz[v]$.
* Ngược lại, phần ngoài gốc trước kia giờ trở thành cây con của $v$.
* Duyệt DFS rerooting để tính $dp[v]$ cho mọi $v$ và cập nhật kết quả tối đa.
## 3. Cài đặt C++
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 200000 + 5;
int n;
vector<int> adj[MAXN];
ll siz[MAXN]; // siz[u] = số đỉnh trong cây con của u khi gốc là 1
ll dp[MAXN]; // dp[u] = tổng điểm khi gốc là u
ll ans = 0;
// Bước 1: dfs1 tính kích thước siz[u]
void dfs1(int u, int p) {
siz[u] = 1;
for (int v : adj[u]) {
if (v == p) continue;
dfs1(v, u);
siz[u] += siz[v];
}
}
// Bước 2: dfs2 thực hiện rerooting và cập nhật ans
void dfs2(int u, int p) {
ans = max(ans, dp[u]);
for (int v : adj[u]) {
if (v == p) continue;
// công thức reroot:
dp[v] = dp[u] - siz[v] + (n - siz[v]);
dfs2(v, u);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// 1) Tính siz[] với gốc tạm là 1
dfs1(1, 0);
// 2) Tính dp[1]
dp[1] = 0;
for (int u = 1; u <= n; ++u)
dp[1] += siz[u];
// 3) Rerooting dfs để tìm giá trị dp[v]
dfs2(1, 0);
cout << ans << "\n";
return 0;
}
```
## 4. Phân tích độ phức tạp
* **DFS1** và **DFS2** mỗi lần đi qua tất cả các đỉnh và cạnh chỉ **một lần**, nên tổng thời gian là $O(n)$.
* Bộ nhớ $O(n)$ cho danh sách kề và mảng.
---
# Hướng dẫn giải bài "Cải thiện đường đi"
## 1. Nhận xét đề bài
* Cho một cây gồm $n$ đỉnh, đánh số từ $1$ đến $n$. Mỗi đỉnh $i$ có một con đường nối với đỉnh $p_i$ (với $i=2\ldots n$).
* Ban đầu tất cả các đường đều "xấu". Ta có thể chọn một tập các đường để "cải thiện".
* Yêu cầu: với mỗi đỉnh $x$ làm thủ đô, tính số cách chọn tập các đường sao cho trên đường đi từ thủ đô $x$ đến bất kỳ đỉnh nào khác có **tối đa 1 đường xấu**.
* Kết quả in theo modulo $10^9+7$.
Link bài tập: https://tritrang.dev/problem/cf543d
## 2. Chuyển bài toán về đếm cách trên cây
Xét cây gốc tại $x$:
* Mỗi cạnh được cải thiện (tốt) hay không (xấu). Ta cần đảm bảo với mọi đỉnh khác, trên đường từ gốc đến đỉnh đó chỉ có tối đa 1 cạnh xấu.
* Tương đương: trong mỗi nhánh con của $x$, ta chỉ được phép để nhiều nhất 1 cạnh xấu trên đường từ $x$ xuống lá.
## 3. Rerooting DP
### 3.1. Định nghĩa DP tại một gốc cố định (root = 0)
Khi xét gốc ban đầu $u$:
* Gọi $dp[u]$ là số cách lựa chọn cải thiện các cạnh trong toàn bộ cây con (subtree) của $u$ sao cho đường từ $u$ đến mọi nút chỉ có tối đa 1 cạnh xấu nội tại nhánh đó.
* Với mỗi con $v$ của $u$, ta có 2 trường hợp:
1. **Không cải thiện** cạnh $u$--$v$: đường xuống toàn bộ subtree $v$ được coi là 1 đoạn xấu duy nhất, nên chỉ có 1 cách.
2. **Cải thiện** cạnh $u$--$v$: lúc này ta đếm tất cả cách trong subtree $v$, là $dp[v]$.
* Do các nhánh độc lập, ta nhân gộp:
$$
dp[u] = \prod_{v\in children(u)} (1 + dp[v]) mod M.
$$
### 3.2. Tính tiền tố và hậu tố
* Để hỗ trợ chuyển gốc (reroot) nhanh, với mỗi nút $u$ xây hai mảng:
* `pref[u][i]` = tích $\prod_{j < i} (1 + dp[child_j])$
* `suf[u][i]` = tích $\prod_{j > i} (1 + dp[child_j])$
* Khi muốn loại bỏ con thứ $i$ khỏi tích gốc, ta lấy `pref[u][i] * suf[u][i]`.
### 3.3. Rerooting: tính DP với mọi gốc
* Bắt đầu từ gốc 0, đã có `dp[]` tính cho cây gốc.
* Đệ quy hàm `reroot(u, parent)`:
1. Ghi `ans[u] = dp[u]` là số cách khi $u$ là thủ đô.
2. Với mỗi con $v$ của $u$:
* Tạm tính `dp[u]` mới khi bỏ nhánh $v$:
```
dp_u_wo_v = pref[u][i] * suf[u][i] % MOD;
// nếu u không phải gốc ban đầu, nhân thêm (1 + dp[parent])
dp_u_wo_v = dp_u_wo_v * (1 + dp[parent]) % MOD;
```
* Cập nhật `dp[v]` khi coi u là con của v:
```
dp[v] = dp[v] * (1 + dp_u_wo_v) % MOD;
```
* Đệ quy: `reroot(v, u)`.
* Khôi phục `dp[u], dp[v]` ban đầu để xử lý các con khác.
## 4. Độ phức tạp
* Xây `dp[]` và `pref`/`suf`: $O(n)$.
* Rerooting duyệt mỗi cạnh hai lần, mỗi lần $O(1)$ phép nhân: $O(n)$.
* Tổng: $O(n)$, đủ cho $n\le 2\cdot10^5$.
## 5. Minh họa mã C++
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 300;
const int MOD = 1000000007;
// g[u]: danh sách con (cây được biểu diễn dưới dạng con trỏ đến các nút con)
// pref[u], suf[u]: mảng tiền tố và hậu tố dùng để tính nhanh tích các dp con trừ một con cụ thể
vector<int> g[N], pref[N], suf[N];
// ans[u]: kết quả cuối cùng khi chọn u làm thủ đô
// dp[u]: số cách cải thiện đường trong cây con gốc tại u (chưa tính phần ngoài cây con này)
int ans[N], dp[N];
// Hàm dfs tính dp[u] cho mỗi nút u theo dạng post-order
// dp[u] = tích (dp[v] + 1) với mọi con v của u
// (dp[v] + 1) tương ứng hai trường hợp: hoặc không cải thiện đường (1 cách) hoặc cải thiện trong subtree v (dp[v] cách)
void dfs(int u) {
dp[u] = 1;
for (int v : g[u]) {
dfs(v);
dp[u] = int((1LL * dp[u] * (dp[v] + 1)) % MOD);
}
// Chuẩn bị tiền tố và hậu tố để hỗ trợ rerooting O(1) cho mỗi con
int left_prod = 1, right_prod = 1;
int sz = g[u].size();
// Tính pref[u][i] = tích (dp[con_j] + 1) với j < i
// suf[u][i] = tích (dp[con_j] + 1) với j > i
for (int i = 0; i < sz; i++) {
int v = g[u][i];
pref[u].push_back(left_prod);
left_prod = int((1LL * left_prod * (dp[v] + 1)) % MOD);
int rv = g[u][sz - 1 - i];
suf[u].push_back(right_prod);
right_prod = int((1LL * right_prod * (dp[rv] + 1)) % MOD);
}
reverse(suf[u].begin(), suf[u].end());
}
// Hàm reroot thực hiện kĩ thuật rerooting DP
// Ta xét lần lượt mỗi nút u làm gốc, và tận dụng kết quả dp[u] để tính ans[u]
// Sau đó, di chuyển gốc từ u xuống từng con v, cập nhật dp[u] và dp[v] tạm thời
// để dfs tiếp tại v và thu được ans[v]
void reroot(int u, int parent = -1) {
// Khi u đang là gốc, số cách cải thiện toàn cỏ cây là dp[u]
ans[u] = dp[u];
int sz = g[u].size();
for (int i = 0; i < sz; i++) {
int v = g[u][i];
// Lưu lại giá trị cũ để khôi phục sau khi recurse
int old_u = dp[u], old_v = dp[v];
// Tính dp[u] mới khi loại bỏ nhánh v (sử dụng pref/suf)
dp[u] = int((1LL * pref[u][i] * suf[u][i]) % MOD);
// Nếu u có parent (tức là u không phải gốc ban đầu), thêm đóng góp của phần ngoài
if (parent != -1) {
dp[u] = int((1LL * dp[u] * (dp[parent] + 1)) % MOD);
}
// Tính dp[v] mới khi coi u là con của v: nhân thêm (dp[u] + 1)
dp[v] = int((1LL * dp[v] * (dp[u] + 1)) % MOD);
// Đệ quy xuống v
reroot(v, u);
// Khôi phục dp[u], dp[v] sau khi trở về
dp[u] = old_u;
dp[v] = old_v;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// Đọc cây: mỗi dòng cho biết parent của i (2..n)
// lưu dưới dạng 0-based
for (int i = 2; i <= n; i++) {
int p;
cin >> p;
g[p - 1].push_back(i - 1);
}
// Bước 1: tính dp cho gốc ban đầu (0)
dfs(0);
// Bước 2: rerooting từ gốc 0, lan truyền kết quả đến tất cả các nút
reroot(0);
// In kết quả: ans[i] tương ứng thủ đô tại i
for (int i = 0; i < n; i++) {
cout << ans[i] << (i + 1 < n ? ' ' : '\n');
}
return 0;
}
```
---
# Hướng dẫn giải bài "Cây xen kẽ"
## 1. Đề bài tóm tắt
Cho cây có **n** nút (1 ≤ n ≤ 2·10⁵), mỗi nút i gán giá trị Vᵢ.
Định nghĩa giá trị hàm alternating trên đường đi đơn giản từ u₁ → u₂ → ⋯ → uₘ là:
$$ A(u_1, u_m) = ∑ \times {i=1..m} (–1)^{i+1} · V*{u_i} $$
Tính tổng A(u, v) cho **tất cả** các đường đi đơn giản (u → v), xem (u, v) có thứ tự, và xuất kết quả mod 10⁹+7.
Link bài tập: https://tritrang.dev/problem/cf960e
## 2. Chuyển thành rerooting DP
### 2.1. Định nghĩa F\[u]
Giả sử đặt tạm gốc cây tại một đỉnh `r`. Khi đó mỗi nút `u` có
```
F[u] =
SUM_{đường đi từ u đi xuống bất kỳ nút x trong subtree của u} A(u → x)
```
Ta chứng minh được công thức đệ quy (bottom-up):
```
F[u] = SIZE[u] * V[u] – ∑_{v con của u} F[v]
```
* `SIZE[u]`: số nút trong subtree u (kể cả u).
* V\[u]: giá trị gắn với nút u.
### 2.2. Di chuyển gốc (Rerooting)
Để tính F\[u] cho mọi u coi là gốc, ta cần rerooting theo 2 bước:
1. **Tách** subtree v khỏi u:
```
// lưu tạm F và SIZE
F_u0 = F[u]; SIZE_u0 = SIZE[u];
F_v0 = F[v]; SIZE_v0 = SIZE[v];
// cập nhật khi bỏ v ra khỏi u
F[u] = F_u0 - SIZE[v] * V[u] + F[v];
SIZE[u] = SIZE_u0 - SIZE[v];
```
2. **Gắn** u vào v:
```
F[v] = F_v0 + SIZE[u] * V[v] - F[u];
SIZE[v] = SIZE_v0 + SIZE[u];
```
Sau đó đệ quy xuống con của v, và **phục hồi** lại giá trị ban đầu trước khi sang nhánh khác.
## 3. Thuật toán chi tiết
1. **Xây dựng cây**: đọc n, V\[1..n], danh sách cạnh. Lưu adjacency list.
2. **DFS1 (bottom-up)** từ gốc 1:
* Tính `SIZE[u]` và `F[u]` theo công thức ở mục 2.1.
3. **DFS2 (top-down rerooting)** từ gốc 1:
* Mỗi khi đến u, cộng `F[u]` vào đáp án chung `ans`.
* Với mỗi con v của u:
* Áp dụng hai bước tách – gắn như trên để cập nhật tạm `F[u]`, `F[v]`, `SIZE[u]`, `SIZE[v]`.
* Gọi đệ quy `dfs2(v, u)`.
* Phục hồi bốn giá trị về ban đầu.
4. **In kết quả**: output `ans mod 10^9+7`.
## 4. Độ phức tạp
* Xây dựng cây và các DFS: $O(n)$.
* Mỗi cạnh được xử lý $2$ lần (một lúc bottom-up, một lúc top-down), tổng $O(n)$.
## Code minh họa C++ đầy đủ
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007;
int n;
vector<ll> V;
vector<vector<int>> adj;
vector<ll> sz, F;
ll ans = 0;
// DFS 1: bottom-up, tính sz[u] và F[u] với gốc ban đầu tại 1
void dfs1(int u, int p) {
sz[u] = 1;
for (int v : adj[u]) if (v != p) {
dfs1(v, u);
sz[u] += sz[v];
}
ll sumF = 0;
for (int v : adj[u]) if (v != p) {
sumF = (sumF + F[v]) % MOD;
}
F[u] = ((sz[u] % MOD) * ((V[u] % MOD + MOD) % MOD) % MOD - sumF + MOD) % MOD;
}
// DFS 2: rerooting, di chuyển gốc từ u xuống các con v
void dfs2(int u, int p) {
// khi đang coi u là gốc, F[u] chứa tổng alternating function cho mọi đường đi bắt đầu tại u
ans = (ans + F[u]) % MOD;
for (int v : adj[u]) if (v != p) {
// lưu giá trị cũ
ll Fu = F[u], Fv = F[v];
ll szu = sz[u], szv = sz[v];
// cập nhật u tách subtree v ra
F[u] = (Fu - (sz[v] % MOD) * ((V[u] % MOD + MOD) % MOD) % MOD + F[v] + MOD) % MOD;
sz[u] = szu - szv;
// cập nhật v gắn subtree u vào
F[v] = (Fv + (sz[u] % MOD) * ((V[v] % MOD + MOD) % MOD) % MOD - F[u] + MOD) % MOD;
sz[v] = szv + sz[u];
dfs2(v, u);
// khôi phục
F[u] = Fu; F[v] = Fv;
sz[u] = szu; sz[v] = szv;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
V.assign(n+1, 0);
for (int i = 1; i <= n; i++) cin >> V[i];
adj.assign(n+1, {});
for (int i = 0; i < n-1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
sz.assign(n+1, 0);
F.assign(n+1, 0);
dfs1(1, 0);
dfs2(1, 0);
cout << (ans % MOD + MOD) % MOD << '\n';
return 0;
}
```
---
Sign in with Wallet
Connect another wallet