/ ZYCode / 题库 /

【ZYCode R6】Conflict

【ZYCode R6】Conflict

Introduction

公交车

在一边,一股黑暗势力正在集结他们的军队。
在另一边,一个秘密联盟宣誓要守护真理的火焰。
如果两个无法和解的宿敌都在为他们最珍视的事物而战,他们是否会为了取得胜利倾尽全力?
如果他们为之而战的是相同的事物,他们又会如何为之拼命?
在与残忍的敌人展开殊死搏斗中...
一名为战斗而生的勇士,一个决心要征服的敌人...
让战斗开始!

Background

冲突,在这片土地上接连上演.
而它们的主角:人,永远存在于世间.

人们有不同的性格,不同的种族,这便是故事的开篇.
在世界之树上,冲突带来的战火始终蔓延.

指环王1:魔戒再现
有的人,将权力紧握手中.
面对同胞的惨死,无动于衷.

指环王1:魔戒再现
有的人,尽管成风之斫.
面对眼前的财宝,却无法定夺.

指环王1:魔戒再现
有的人,似乎心无旁骛.
但在冲突的作用下,仍与他人交恶.

战争无可避免,
人们只能铤而走险.

指环王2:双塔奇兵
有人勠力同心,
只求回天改命.

指环王2:双塔奇兵
有人力摧敌阵,
为报昨日之恨.

指环王2:双塔奇兵
无论胜败,
局部的毁灭已经到来.

曾经的联盟不再,
留下的只有尸骸.

局部可以被修复,
但如果不加抵抗,终将万劫不复.

黑夜伴随硝烟散去,
树枝上长出了一抹新绿.

难以磨平战火的创伤,
只求眼下百姓安康.

战火磨练出真金,
新王加冕也未忘初心.

时机已到,今日起兵!
再让那鲜血染红衣襟!

冲突可能是病,但并非无药可救:
人类的未来,在冲突中造就!

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\)

题目背景取自 电影 指环王 The Lord of the Rings

信息

ID
1035
难度
1919810
分类
树结构 点击显示
标签
递交数
10
已通过
1
通过率
10%
上传者