QOJ.ac

QOJ

Límite de tiempo: 1.5 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓

#14720. 77G 網路

Estadísticas

喵之國的地圖可以視為一棵有 $n$ 個節點與 $n - 1$ 條邊的有根樹,其中節點代表城市,邊代表連接兩座城市的道路。首都位於樹根,即節點 $1$。

現在喵之國想在一些城市安裝全新的 77G 網路基地台。為了確保每條道路都有足夠的網路品質,每條道路的兩個端點城市中至少要有一個安裝基地台。然而,由於未知的技術問題,網路系統有 $m$ 個故障。故障 $i$ 可以描述如下:如果在城市 $x_i$ 安裝了基地台,那麼在 $x_i$ 的子樹中,所有與 $x_i$ 的距離恰好為 $y_i$ 的城市都不能安裝基地台;否則基地台之間會互相干擾而無法使用。

請幫助喵之國選擇一些城市,使得在這些城市安裝基地台能滿足上述所有要求。如果不存在合法方案,請輸出 No。

輸入格式

每個測試檔案包含多筆測試資料。第一行包含測試資料的數量 $T$($1 \le T \le 10^3$)。接下來是各筆測試資料的描述。

每筆測試資料的第一行包含一個整數 $n$($2 \le n \le 2 \times 10^5$),表示城市的數量。

第二行包含 $n - 1$ 個整數 $f_2, f_3, \dots, f_n$($1 \le f_i < i$),其中 $f_i$ 表示城市 $i$ 的父節點。

第三行包含一個整數 $m$($0 \le m \le 2 \times 10^5$),表示故障的數量。

接下來的 $m$ 行,每行包含兩個整數 $x_i$ 與 $y_i$($1 \le x_i, y_i \le n$),表示第 $i$ 個故障。可能會存在兩個完全相同的故障。

對於每個測試檔案,保證所有測試資料中 $n$ 的總和不超過 $2 \times 10^5$,且所有測試資料中 $m$ 的總和不超過 $2 \times 10^5$。

輸出格式

對於每筆測試資料,若不存在合法方案,請輸出一行 No。

否則,請輸出三行來表示你的方案:

  • 在第一行輸出 Yes。
  • 在第二行輸出一個整數 $c$,表示你選擇的城市數量。
  • 在第三行輸出 $c$ 個相異整數,表示你選擇的城市。

若有多個合法方案,你可以輸出任意一個。輸出方案時,你可以以任意順序輸出這 $c$ 座城市。

範例

範例輸入 1

3
6
1 1 2 2 4
2
1 3
2 1
6
1 1 2 2 4
6
1 1
1 2
1 3
2 1
2 2
2 1
8
1 1 3 1 1 2 4
10
1 2
3 2
1 3
5 1
6 1
3 2
4 1
3 2
5 1
3 1

範例輸出 1

Yes
4
5 3 4 1
No
No

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.