a332. TOI 2023/10 潛力組：電力配送

題目描述

城市有 N 座電廠，現有配送網路在忽略方向後是一棵樹，每條路線只允許往一個方向配送電力。市長考慮指定一座電廠為唯一發電來源，並反轉部分路線方向，使電力能從該電廠沿有向路線送到其他所有電廠。

給定 K 個候選電廠，請分別計算選定它們時需要反轉幾條路線。每個候選情況獨立計算，都以原始網路為準。

輸入格式

第一行為整數 N、K，2 ≤ N ≤ 10^4，1 ≤ K ≤ N。

接著 N−1 行，每行為整數 S、T，1 ≤ S, T ≤ N，表示原本有一條由 S 通往 T 的單向配送路線。保證忽略方向後，任意兩座電廠都可連通。

最後一行有 K 個整數 P_i，1 ≤ P_i ≤ N，依序為候選中央電廠編號。

原題分組限制：30 分：K = 1。30 分：電廠依編號排成一直線，每條邊皆滿足 |S−T| = 1。40 分：無額外限制。

輸出格式

輸出 K 個整數，以空白分隔。第 i 個整數為選擇 P_i 作為唯一發電來源時，需要反轉的路線數。

範例 1

輸入：

6 1
1 2
4 5
3 4
3 2
6 5
3

輸出：

2

範例 2

輸入：

6 3
1 4
1 2
3 1
2 6
5 6
4 3 1

輸出：

3 1 2

來源

TOI 2023 年 10 月歷屆題〈電力配送〉，依官方 PDF 重新整理。

官方原題：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202310/Power.pdf

標籤：TOI 歷屆