在一片神秘的魔法森林中，有 $N$ 個節點（編號 $1$ 到 $N$），由 $N-1$ 條邊連成一棵樹。每個節點上有一盞魔法燈，魔法燈會散發一種顏色的光芒。顏色用整數表示，範圍為 $1$ 到 $C$。
森林的精靈們喜歡沿著樹徑旅行。當他們從節點 $u$ 走到節點 $v$（沿著唯一的路徑），他們會觀察路徑上所有節點（包括 $u$ 和 $v$）的魔法燈顏色。如果某種顏色的燈在路徑上出現了奇數次，他們認為這種顏色是「神秘」的。他們想知道，對於一條給定的路徑 $u→v$，有多少種顏色是神秘的。
然而，魔法燈的顏色會隨著時間改變！森林裡有兩種事件：
-
更新事件：給定節點 $x$ 和新的顏色 $c$，將節點 $x$ 的魔法燈顏色改為 $c$。
-
查詢事件：給定兩個節點 $u$ 和 $v$，詢問從 $u$ 到 $v$ 的路徑上，出現次數為奇數的顏色種類數。
你需要高效地處理這些事件。
第一行包含三個整數 $N$, $C$, $Q$，分別代表節點數量、顏色總數、事件總數。
接下來 $N-1$ 行，每行兩個整數 $a$, $b$，表示節點 $a$ 和 $b$ 之間有一條邊。
接下來一行，包含 $N$ 個整數 $col[1..N]$，表示初始時每個節點的顏色。
接下來 $Q$ 行，每行描述一個事件：
-
若事件以
U開頭，則後接兩個整數 $x$ $c$，表示將節點 $x$ 的顏色改為 $c$。 -
若事件以
Q開頭，則後接兩個整數 $u$ $v$，表示詢問路徑 $u→v$ 上的神秘顏色數量。
-
$1 ≤ N, Q ≤ 2*10^5$
-
$1 ≤ C ≤ 1000$
-
$1 ≤ col[i], c ≤ C$
-
保證輸入的是一棵樹
對於每個查詢事件，輸出一行一個整數，表示答案。
1 1 3 1 Q 1 1 U 1 1 Q 1 1
1 1
不公開 測資點#0 (5%): 0.3s , <10M
不公開 測資點#1 (5%): 0.3s , <10M
不公開 測資點#2 (5%): 0.3s , <10M
不公開 測資點#3 (5%): 0.3s , <10M
不公開 測資點#4 (5%): 0.3s , <10M
不公開 測資點#5 (5%): 0.3s , <10M
不公開 測資點#6 (5%): 0.3s , <10M
不公開 測資點#7 (5%): 0.3s , <10M
不公開 測資點#8 (5%): 0.3s , <10M
不公開 測資點#9 (5%): 0.3s , <10M
不公開 測資點#10 (5%): 0.3s , <10M
不公開 測資點#11 (5%): 0.3s , <10M
不公開 測資點#12 (5%): 0.3s , <10M
不公開 測資點#13 (5%): 0.3s , <10M
不公開 測資點#14 (5%): 0.3s , <10M
不公開 測資點#15 (5%): 0.3s , <10M
不公開 測資點#16 (5%): 0.3s , <10M
不公開 測資點#17 (5%): 0.3s , <10M
不公開 測資點#18 (5%): 0.3s , <10M
不公開 測資點#19 (5%): 0.3s , <10M
2026/3/1 加強測資 至 $1 ≤ N, Q ≤ 2*10^5$
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||