【ZYCode R6】Conflict
Introduction
在一边，一股黑暗势力正在集结他们的军队。
在另一边，一个秘密联盟宣誓要守护真理的火焰。
如果两个无法和解的宿敌都在为他们最珍视的事物而战，他们是否会为了取得胜利倾尽全力？
如果他们为之而战的是相同的事物，他们又会如何为之拼命？
在与残忍的敌人展开殊死搏斗中...
一名为战斗而生的勇士，一个决心要征服的敌人...
让战斗开始！
Background
冲突,在这片土地上接连上演.
而它们的主角:人,永远存在于世间.
人们有不同的性格,不同的种族,这便是故事的开篇.
在世界之树上,冲突带来的战火始终蔓延.
有的人,将权力紧握手中.
面对同胞的惨死,无动于衷.
有的人,尽管成风之斫.
面对眼前的财宝,却无法定夺.
有的人,似乎心无旁骛.
但在冲突的作用下,仍与他人交恶.
战争无可避免,
人们只能铤而走险.
有人勠力同心,
只求回天改命.
有人力摧敌阵,
为报昨日之恨.
无论胜败,
局部的毁灭已经到来.
曾经的联盟不再,
留下的只有尸骸.
局部可以被修复,
但如果不加抵抗,终将万劫不复.
黑夜伴随硝烟散去,
树枝上长出了一抹新绿.
难以磨平战火的创伤,
只求眼下百姓安康.
战火磨练出真金,
新王加冕也未忘初心.
时机已到,今日起兵!
再让那鲜血染红衣襟!
冲突可能是病,但并非无药可救:
人类的未来,在冲突中造就!
Only through conflict do we evolve!
Description
以下是 形式化 题面描述
现在,已知一棵树,有 \(n\) 个节点,编号为 \(1\) 至 \(n\) ,以 \(1\) 为根,每个节点代表一个 人.
每个 人 的 力量值 为 \(V_i\) ,每个子树代表那里的人们具有某种相同的 性格
给出\(m\)条 冲突源 , 每条可以描述为:
\(u\)对于\(v\)子树代表的 性格 产生了 \(k\) 点 仇恨值 ,并发泄出来,若不加反抗,将造成巨量 毁灭值.
对于每条 冲突源 ,我们认为, \(v\) 子树里任意两个人等概率进行 协力.
这里,若 \(x\) , \(y\) 两人进行了 协力, 他们首先会认为在 \(v\) 子树中,而且既不在 \(x\) 子树中,也不在 \(y\) 子树中,同时又不在 \(x\) , \(y\) 路径上的人为 背叛者 ,相应的,除此之外 \(v\) 子树中的人被称为 起义者 (包括 \(x\) , \(y\) ).
于是,一次 战斗 无可避免,在 战斗 中, 起义者 对被认为是 背叛者 的人产生了\((V_x+V_y)^2\)点 毁灭值 .(注意,即使不存在 背叛者 他们仍然会造成这 毁灭值 )
然后,这次 战斗 中有若干 局部战场, 每个 局部战场 中包含一名 起义者 ,一名 背叛者, 以及 \(u\) ,造成的 毁灭值 为三人的 力量值 之积.
战斗 旷日持久,每种不同的 局部战场 发生了恰好一次.
最后, 战斗 结束后,记 已经产生的毁灭值 为\(D\).
胜利方 将在额外造成 \((k+V_u)^3\) 点 毁灭值.
对于每条 冲突源 , 输出 总毁灭值的期望值 .
保证 \(u\) 不在 \(v\) 的子树中
Format
Input
第一行两个整数 \(n\) , \(m\)
第二行 \(n\) 个整数,表示\(V_1\)到\(V_n\).
接下来 \(n-1\) 行每行两个整数 \(u\),\(v\)描述一条边.
接下来 \(m\) 行每行描述一条 冲突源 ,顺序: \(u\) , \(v\) , \(k\) .
Output
\(m\) 行,对于每个 冲突源,输出答案,对\(1226999999\)取模.
Sample 1
Input
7 2
1 2 3 4 5 6 7
1 2
1 3
3 4
3 5
4 6
4 7
2 4 5
2 3 5
Output
473
736200575
Limitation
1s, 1024KiB for each test case.
Hint
所有输入都是正整数.
| 子任务 | 占比 | \(n\le\) | \(m\le\) | \(V_i\le\) |
|---|---|---|---|---|
| Subtask1 | \( 20\% \) | \(100\) | \(100\) | \(10^6\) |
| Subtask2 | \( 20\% \) | \(1000\) | \(1000\) | \(10^6\) |
| Subtask3 | \( 20\% \) | \(10^5\) | \(10^5\) | \(1\) |
| Subtask3 | \( 40\% \) | \(10^5\) | \(10^5\) | \(10^6\) |
