1421 . 深度陣列

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

boss_zz

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

35.3% (12/34)

Tags

ioicamp ioicamp-2026

Description

在寫跟樹有關的競程題目時，我們常常會需要求出一棵有根樹的「深度陣列」，要怎麼定義什麼是深度陣列呢？首先，給定一棵樹，你需要選定一個根 $r$，接著，你會生成一個陣列 $d$，滿足
$$
d_i = \text{dis}(r, i)
$$
其中 $\text{dis}(u, v)$ 是 $u$ 到 $v$ 在樹上的最短路徑。

現在，給你一棵樹和一個不符合深度陣列定義的陣列 $d_1, d_2, \ldots, d_N$，你要求出你最少要修改幾個數字，才能讓這個陣列成為某個根 $r$ 的深度陣列。

換句話說，令 $f(r)$ 代表以 $r$ 為根的深度陣列中，$d_i \neq \text{dis}(r, i)$ 的 $i$ 個數，求
$$
\min_{1\leq r\leq N} f(r)
$$

Input Format

輸入首行會有一個正整數 $N$，代表樹的節點數量。

次行會有一個長度為 $N$ 的整數陣列 $d_1, d_2, \ldots, d_N$，代表需要被修改的陣列。

接下來 $N-1$ 行，第 $i$ 行兩個正整數 $u_i, v_i$，代表第 $i$ 邊連接著的兩個節點編號為 $u_i, v_i$。

  • $1\le N\le 3\times 10^ 5$
  • $0\le d_i\le N$
  • $1\leq u_i, v_i \leq N$
  • 保證輸入為一合法的樹

Output Format

輸出一個整數，代表最少需要修改的位置數量。

Sample Input 1

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

Sample Output 1

3

Sample Input 2

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

Sample Output 2

3

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資。 0
2 0~47 無特別限制。 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 1048576 65536 1 2
1 4000 1048576 65536 1 2
2 4000 1048576 65536 2
3 4000 1048576 65536 2
4 4000 1048576 65536 2
5 4000 1048576 65536 2
6 4000 1048576 65536 2
7 4000 1048576 65536 2
8 4000 1048576 65536 2
9 4000 1048576 65536 2
10 4000 1048576 65536 2
11 4000 1048576 65536 2
12 4000 1048576 65536 2
13 4000 1048576 65536 2
14 4000 1048576 65536 2
15 4000 1048576 65536 2
16 4000 1048576 65536 2
17 4000 1048576 65536 2
18 4000 1048576 65536 2
19 4000 1048576 65536 2
20 4000 1048576 65536 2
21 4000 1048576 65536 2
22 4000 1048576 65536 2
23 4000 1048576 65536 2
24 4000 1048576 65536 2
25 4000 1048576 65536 2
26 4000 1048576 65536 2
27 4000 1048576 65536 2
28 4000 1048576 65536 2
29 4000 1048576 65536 2
30 4000 1048576 65536 2
31 4000 1048576 65536 2
32 4000 1048576 65536 2
33 4000 1048576 65536 2
34 4000 1048576 65536 2
35 4000 1048576 65536 2
36 4000 1048576 65536 2
37 4000 1048576 65536 2
38 4000 1048576 65536 2
39 4000 1048576 65536 2
40 4000 1048576 65536 2
41 4000 1048576 65536 2
42 4000 1048576 65536 2
43 4000 1048576 65536 2
44 4000 1048576 65536 2
45 4000 1048576 65536 2
46 4000 1048576 65536 2
47 4000 1048576 65536 2
Submit
Back to Top