---
title: Run Road Solution
---

$\Huge\text{Run Road Solution}$

----------

:::info
🔗 Links:
📌 Tags: `math` `graph`
✍ Writer: Hoàng Việt
📄 Content:
[TOC]
:::

---------

## Thuật toán

Thay vì tính tổng giá trị độ dài của tất cả các vòng chạy có độ cao vòng chạy đúng bằng $t$, hãy tính tổng giá trị độ dài của tất cả các vòng chạy có độ cao vòng chạy bé hơn hoặc bằng $t$.

Gọi $f(val)$ là tổng giá trị độ dài của tất cả các vòng chạy có độ cao vòng chạy bé hơn hoặc bằng $val$.

Kết quả sẽ là $f(t) - f(t - 1)$.

Để tính $f(val)$:

Ta sẽ xây dựng lại một đồ thị mới gồm các cạnh $(u, v)$ mà độ cao của đỉnh $u$ và đỉnh $v$ đều bé hơn hoặc bằng $val$.

Xét tất cả các cạnh $(u, v)$ trong đồ thị mới, số lần được tính vào kết quả sẽ là số bộ ba $(x, y, z)$ mà có đi qua cạnh đó.

Khi cắt cạnh $(u, v)$ ra khỏi đồ thị mới:

- Gọi $S_1$ là số lượng đỉnh cùng thành phần liên thông với $u$
- Gọi $S_2$ là số lượng đỉnh cùng thành phần liên thông với $v$

Xét 2 trường hợp:

- Trong bộ ba $(x, y, z)$ có 2 đỉnh cùng thành phần liên thông với $u$ và 1 đỉnh cùng thành phần liên thông với $v$. Số lượng bộ ba thuộc trường hợp này là $C_{S_1}^2$ * $S_2$.
- Trong bộ ba $(x, y, z)$ có 1 đỉnh cùng thành phần liên thông với $u$ và 2 đỉnh cùng thành phần liên thông với $v$. Số lượng bộ ba thuộc trường hợp này là $C_{S_2}^2$ * $S_1$.

Trong cả hai trường hợp này thì cạnh $(u, v)$ đều được tính vào kết quả hai lần.

Vậy với mỗi cạnh $(u, v)$ thì cộng thêm một lượng $C_{S_1}^2$ * $S_2$ * $2$ + $C_{S_2}^2$ * $S_1$ * $2$
vào $f(val)$.

Ta có thể dễ dàng tính $S_1$ và $S_2$ bằng cách $DFS$ với mỗi thành phần liên thông để tính trước mảng $sum$ với $sum_u$ là số lượng đỉnh trong cây con gốc $u$. Và khi xét tới cạnh $(u, v)$ với $v$ là cha của $u$ thì $S_1$ = $sum_u$ và $S_2$ = $NumNode - sum_u$ với $NumNode$ số lượng đỉnh trong thành phần liên thông đó.

Độ phức tạp $O(N)$.

-----------------

Tham khảo code mẫu ở [đây](https://ideone.com/xh62NG).