本題為 "Country" Road (Easy Version) 的續題
在上一題有提到，
有一群人想建國，
而且也把土地分了級。
當然分級後的土地應該要對所管轄的土地有控制權，
因此一旦土地 $v$ 被列為土地 $u$ 的管轄範圍，
則土地 $v$ 的人民、土地、所管轄的土地皆會被算在土地 $u$ 裡。
但這也引發了原本土地擁有人的不滿，
當然，
原本就沒有算在國土裡的土地就沒有意見 (代表他們不會參加內亂) 。
雖然他們已經很努力的維持政權，
但還是發生了內亂，
依照該政府的統計共有 $Q$ 場內亂。
很不巧的是，
在建國初期為了要防禦外敵，
每塊土地都分配到了該國的秘密武器 -- Destroyer (連不算在國土裡的都有分到)
它的威力極大，
所到之處皆是荒土。
幸好在發明之時，
有發明對抗他的武器 -- 神奇的晾衣桿來福槍
這把來福槍的攻擊力是 $\frac{目前 Destroyer 剩餘的血量}{2}$，
也就是直接把 Destroyer 的血量砍半。
不過因為這把槍需要很長的時間來注入魔力，
所以前面防守的比拚才是重點，
因此假設土地 $u$ 和土地 $v$ 互相發動戰爭，
如果 $u$ 管轄著 $v$ (包括間接管轄)，
則 $v$ 必定會敗北，
Destroyer 會直接被 $u$ 的來福槍攻擊，
反之亦然。
此外上級機關還有一個優勢，
但如果 $u$ 和 $v$ 誰都沒有管轄誰，
那就兩邊的 Destroyer 都會受到傷害。
此外上級機關還有一個優勢，
當初為了應付大型戰爭，
上級機關的 Destroyer 的血量為所有下級機關 Destroyer 的血量再加上自己 Destroyer 的血量，
所以當上級機關的 Destroyer 受到傷害時，
會以各機關目前剩餘的血量為權重，
分配所承受的傷害，
換句話說，
就是連同下級機關的 Destroyer 血量也要減少一半，
這樣就可以確保上級機關的 Destroyer 的存活。
但下級所受到的傷害上級不必分擔，
這也是為什麼下級必定敗北的原因。
由於政府為了要再度統一國家，
所以打算等地方拚個兩敗俱傷後再進行統一，
因此統計各地 Destroyer 的血量變得非常重要。
當然，
Destroyer 是由中央發配，
所以中央必定知道各地 Destroyer 的初始血量 $H_i$ 是多少。(當時在趕工，所以品質不一)
請依照每次的內亂幫忙計算兩邊 Destroyer 的血量各剩多少
*間接管轄指的是 $u$ 管轄 $v$，$v$ 管轄 $k$，則 $u$ 間接管轄 $k$，在更多層的關係時亦成立。
*上級機關指的是只要有直接或間接管轄的關係，被管轄的就是下級機關，反之則是上級。
*初始血量指的是單個 Destroyer 的血量
$N\quad M$
$u_1\quad v_1\quad W_1$
$u_2\quad v_2\quad W_2$
$...$
$u_M\quad v_M\quad W_M$
$H_1\quad H_2\quad H_3\quad ...\quad H_N$
$Q$
$u_1\quad v_1$
$u_2\quad v_2$
$...$
$u_Q\quad v_Q$
對每筆 $Q$ 輸出兩地的 Destroyer 剩餘的血量
誤差在 $10^{-6}$ 以內皆判為正確答案
$H_{u_1}\quad H_{v_1}$
$H_{u_2}\quad H_{v_2}$
$...$
$H_{u_Q}\quad H_{v_Q}$
5 5 1 2 1 1 5 2 1 4 4 2 3 5 3 5 3 2 2 2 2 3 3 2 4 3 5 2 5
1.000000000 1.000000000 1.000000000 4.000000000 0.500000000 2.000000000
管轄的關係如下 (第一個為上級後續為其下級)
1 2 3 4 5
2
3
4
5 3
所以
$H_1$ 會變成 $H_1+H_2+H_3+H_4+H_5$
$H_5$ 會變成 $H_3+H_5$
(注意: 上面的等式不能將變數互相帶入)
而當 $H_3$ 的血量改變時
$H_1、H_5$ 也會受到影響
但反過來時不成立
$1\leq N, M, Q\leq 10^5$
$1\leq \forall W_i\leq 10^{12}$
$1\leq \forall u_i, \forall v_i\leq N$
$u_i \neq v_i$
$1\leq \forall H_i\leq 10^4$
所有輸入皆為整數
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||