#P4623. Styx
Styx
Styx
题目描述
行动 Styx 中,反物质武器的位置用树上的路径加密。给定一棵有 个节点的树,根为节点 ,节点 的权值是 。
对正整数 定义
$$f(t)=\sum_{j=1}^t\gcd(j,t),\qquad g(t)=\sum_{d\mid t} f(d).$$对每个节点 ,令 为从根到 的路径上所有节点权值的乘积,包含根和 。令 为以 为根的子树节点数,包含 。定义
一条查询给两个节点 。设从 到 的路径依次为 。从 开始,依序在右侧叉乘 ,求最后的向量。如果 ,结果就是 。
这里两个向量的叉积定义为
$$(x_1,x_2,x_3)\times(y_1,y_2,y_3)= (x_2y_3-x_3y_2,\ x_3y_1-x_1y_3,\ x_1y_2-x_2y_1).$$输入格式
第一行两个整数 ,分别表示节点数和查询数。第二行 个整数 。接下来 行各有两个整数,表示树的一条无向边。其后给出 对整数 。树边与查询之间可能有一个空行。
输出格式
每条查询输出一行三个整数,为结果向量的三个分量分别对 取模后的非负余数,范围为 到 。
3 3
9 4 9
1 2
1 3
1 1
3 2
3 3
27 4 3
999988451 419872 385168
405 12 1
样例解释
第二个查询的路径是 。向量依次为 、、。先叉乘前两个向量,再与第三个叉乘,得到 ,取非负余数后得到样例的第二行。
数据范围
,,。原题标出的权值上限为 ,本题库部分测试中有 。