IOIC 2025 題目已公開！ 連結
YTP 2025 題目已上線！ 連結
程式解題社網站 程式解題社網站上線了！
Rejudge 公告 23 已加強測資並 rejudge
910 . 聖誕樹
TopCoder
Tags
Description
聖誕樹是一個由 $N$ 個節點與 $N-1$ 條邊形成的連通圖，每個節點分別有綠色的燈泡（用 G 表示）或紅色的燈泡（用 R 表示）。因為聖誕節結束了， Alice 跟 Bob 決定要來把聖誕樹上的燈泡收拾一下。
但是，收拾聖誕樹並不是一件簡單的事，於是，他們決定今天使收拾一條鍊上面的燈泡。流程如下：
- 首先，Alice 跟 Bob 分別選一個節點，今天就收拾兩人所選的節點上的最短路徑上的點（包含所選的兩點）
- 將鍊上的紅色燈泡放到 Alice 的籃子中， 綠色燈泡則放在 Bob 的籃子中
但是，他們發現一件事情：他們忘記買籃子了。為了估算他們需要買多大的籃子，Alice 希望你輸出在兩個人選的節點都是隨機的情況下， Alice 跟 Bob 的籃子中裝較多燈泡的籃子大小期望值為多少？
請輸出此數字對 $998244353$ 取模的結果。可以證明這個數字可以被表示成最簡分數 $\frac{x}{y}$，且 $y$ 不為 $998244353$ 的倍數。請輸出 $x \times y^ {-1} \text{ mod } 998244353$，其中 $y^ {-1}$ 是一個在 $1$ 跟 $998244352$ 之間的整數，滿足 $y \times y^ {-1} \equiv 1 \pmod{998244353}$。
Input Format
輸入第一行為一個整數 $N$ ， 表示聖誕樹的節點數
接下來，輸入一個長度為 $N$ 的字串，字元只會是 R 或 G，表示各個節點的燈泡顏色。
最後輸入 $N-1$ 行，每行輸入兩個整數 $u,v$ ，表示聖誕樹上有一條連接 $u$, $v$ 的邊。
保證聖誕樹上任兩點都可以互相抵達。
- $2\le N \le 2 \times 10 ^ 5$
- $1 \le u,v \le N$
Output Format
輸出一個整數，表示在兩人都隨機選擇節點的情況下，每次較大的籃子大小的期望值。
Sample Input 1
2 RG 1 2
Sample Output 1
1
Sample Input 2
5 RGRGR 1 2 2 3 3 4 4 5
Sample Output 2
479157291
Hints
對於範例測資一，總共（Alice, Bob）分別有 $\frac{1}{4}$ 的機率選到以下四種狀況:
- $(1,1):\max($ 綠色燈泡數量，紅色燈泡數量 $)= \max(0,1) = 1$
- $(1,2):\max($ 綠色燈泡數量，紅色燈泡數量 $)= \max(1,1) = 1$
- $(2,1):\max($ 綠色燈泡數量，紅色燈泡數量 $)= \max(1,1) = 1$
- $(2,2):\max($ 綠色燈泡數量，紅色燈泡數量 $)= \max(1,0) = 1$
因此，答案為 $\frac{1}{4} \times 1 + \frac{1}{4} \times 1 + \frac{1}{4} \times 1 + \frac{1}{4} \times 1 = 1$
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~14 | $N \le 2000$ | 20 |
| 3 | 0~33 | 無額外限制 | 80 |