# Lời giải bài Network

### Tác giả: Võ Khắc Triệu, I2023

## 1. Tóm tắt đề
Cho cây $G$ có trọng số gồm $n$ $(1 \le n \le 10^5)$ đỉnh, các cạnh được đánh số từ $1$ đến $n - 1$, trả lời $m$ $(1 \le m \le 10^5)$ truy vấn thuộc $2$ dạng sau:
- $P\ a\ b\ c$: Trên đường đi từ $a$ đến $b$ có bao nhiêu cạnh có trọng số $\le c$.
- $T\ i\ c$: Nếu xóa cạnh thứ $i$ thì miền liên thông chứa đỉnh $v_i$ có bao nhiêu cạnh có trọng số $\le c$.

## 2. Thuật toán ngây thơ

- Đề nói gì làm nấy, xử lý các truy vấn trong thời gian tuyến tính $O(n)$
- Độ phức tạp: $O(m \times n)$

## 3. Cải tiến

### a. Tiền xử lý
- Nhận thấy rằng, ta cần biểu diễn cây dưới dạng cấu trúc dữ liệu khác (**HLD**, **Euler Tour**, ...) để có thể dễ dàng xử lý các truy vấn hơn. Trong lời giải này sẽ chỉ giải thích thuật dùng **Euler Tour**.

**[Tìm hiểu về HLD](https://vnoi.info/wiki/algo/data-structures/heavy-light-decomposition.md)**
**[Tìm hiểu về Euler Tour](https://usaco.guide/CPH.pdf#page=174)**

- **Nhận xét**: Giả sử ta có đáp án của truy vấn $P\ a\ b\ c$ và ta muốn trả lời đáp án cho truy vấn $P\ a\ b\ (c + 1)$, ta chỉ cần xét thêm các cạnh có trọng số $c + 1$ (tương tự với truy vấn loại $T$).
$\rightarrow$ Xử lý **offline**
- Ta sẽ sắp xếp lại các cạnh và các truy vấn theo thứ tự tăng dần về trọng số. Ta sẽ dựng một cây mới $G'$ và cập nhật trọng số theo giá trị đang xét.
- Giả sử xét tới giá trị $c$, nếu trong cây $G$ cạnh có trọng số $\le c$ thì trong cây $G'$ cạnh sẽ có trọng số là $1$, ngược lại là $0$.
- **Tính chất quan trọng của Euler Tour**: Xét một đỉnh $u$ trên cây. Giả sử cây con gốc $u$ có $r$ đỉnh và có vị trí trên **Euler Tour** là $p$.
$\rightarrow$ Các nút từ vị trí $p$ đến $p + r - 1$ trên **Euler Tour** sẽ thuộc cây con gốc $u$.

### b. Định nghĩa chung

- $sz_i$ là số đỉnh của cây con gốc $i$ trên cây $G$.
- $e_i$ là số hiệu đỉnh trên vị trí thứ $i$ của **Euler Tour**.
- $pos_i$ là vị trí của đỉnh thứ $i$ trên **Euler Tour**

### c. Truy vấn loại P

#### Định nghĩa
- Gọi $p_i$ là tổng trọng số từ gốc tới $i$.

#### Cập nhật
- Giả sử cập nhật trọng số của cạnh $u - v$ ($u$ gần gốc hơn $v$) từ $0$ thành $1$ trên đồ thị $G'$, thì với mọi đỉnh $i$ nằm trong cây con gốc $v$, $p_i$ tăng lên $1$.
$\rightarrow p_{e_i} = p_{e_i} + 1\ \forall\ pos_v \le i \le pos_v + sz_v - 1$
$\rightarrow$ Dùng cấu trúc dữ liệu cập nhật đoạn (**Fenwick Tree**, **Segment Tree**).

#### Trả lời
- Dễ thấy, đáp án cho truy vấn $a\ b$ là $p_a + p_b - 2 \times p_{lca(a, b)}$, với $lca(a, b)$ là tổ tiên chung thấp nhất của $a$ và $b$.

**[Tìm hiểu về LCA](https://vnoi.info/wiki/algo/data-structures/lca-binlift.md)**

Cả thao tác cập nhật và trả lời đều tốn $O(log(n))$.

### d. Truy vấn loại T

#### Định nghĩa
- Gọi $t_i$ là tổng trọng số của các cạnh từ $u$ đến các con trực tiếp của $u$ trên đồ thị $G'$
- Gọi $s_i$ là tổng của $t_j$ với mọi $j$ thuộc cây con gốc $i$
$\rightarrow s_i = \sum_{j = pos_i}^{pos_i + sz_i - 1} t_{e_j}$

#### Cập nhật
- Giả sử cập nhật trọng số của cạnh $u - v$ ($u$ gần gốc hơn $v$) từ $0$ thành $1$ trên đồ thị $G'$, thì $t_u$ tăng lên $1$

#### Trả lời

Ta sẽ bài toán thành $2$ trường hợp:

##### Trường hợp 1: $u_i$ là cha của $v_i$

- Dễ thấy, trong trường hợp này, khi cắt cạnh $u_i - v_i$ thì miền liên thông chứa $v_i$ sẽ chính là cây con gốc $v_i$
$\rightarrow$ Đáp án sẽ là $s_{v_i}$

##### Trường hợp 2: $v_i$ là cha của $u_i$

- Tương tự, trong trường hợp này, khi cắt cạnh $u_i - v_i$ thì miền liên thông chứa $u_i$ sẽ chính là cây con gốc $u_i$
$\rightarrow$ Các cạnh **chưa bị xóa** không thuộc cây con gốc $u_i$ sẽ thuộc miền liên thông chứa $v_i$.
- Ngoài ra, vì $v_i$ là cha của $u_i$
$\rightarrow$ Các cạnh không thuộc cây con gốc $v_i$ sẽ thuộc miền liên thông chứa $v_i$.
$\rightarrow$ Đáp án sẽ là $s_{root} - s_{v_i}$ với root là gốc của cây.

Ta có thể dễ dàng tính được $s_i$ bằng dùng các cấu trúc dữ liệu truy vấn đoạn (**Fenwick Tree**, **Segment Tree**).

Cả thao tác cập nhật và trả lời đều tốn $O(log(n))$.

### Độ phức tạp: $O(m \times log(n))$

### Code mẫu: [Link](https://ideone.com/cYvDjO)
### Tag: Tree Algorithm, Data Structure