#P4623. Styx

    ID: 2952 传统题 3000ms 128MiB 尝试: 93 已通过: 13 难度: 8 上传者: 标签>难度分类提高+/省选-数论狄利克雷卷积约数个数乘积公式线性筛最小质因子预处理逆元线性递推枚举与搜索深度优先搜索计算几何叉积线性代数与代数矩阵乘法树算法树上倍增LCACF2500By

Styx

Styx

题目描述

行动 Styx 中,反物质武器的位置用树上的路径加密。给定一棵有 nn 个节点的树,根为节点 11,节点 ii 的权值是 AiA_i。

对正整数 tt 定义

$$f(t)=\sum_{j=1}^t\gcd(j,t),\qquad g(t)=\sum_{d\mid t} f(d).$$

对每个节点 ii,令 S(i)S(i) 为从根到 ii 的路径上所有节点权值的乘积,包含根和 ii。令 s(i)s(i) 为以 ii 为根的子树节点数,包含 ii。定义

F(i)=(g(S(i)),4i,s(i)).F(i)=(g(S(i)),4i,s(i)).

一条查询给两个节点 x,yx,y。设从 xx 到 yy 的路径依次为 v0=x,v1,…,vℓ=yv_0=x,v_1,\ldots,v_\ell=y。从 F(v0)F(v_0) 开始,依序在右侧叉乘 F(v1),…,F(vℓ)F(v_1),\ldots,F(v_\ell),求最后的向量。如果 x=yx=y,结果就是 F(x)F(x)。

这里两个向量的叉积定义为

$$(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).$$

输入格式

第一行两个整数 n,mn,m,分别表示节点数和查询数。第二行 nn 个整数 A1,…,AnA_1,\ldots,A_n。接下来 n−1n-1 行各有两个整数,表示树的一条无向边。其后给出 mm 对整数 x,yx,y。树边与查询之间可能有一个空行。

输出格式

每条查询输出一行三个整数,为结果向量的三个分量分别对 109+710^9+7 取模后的非负余数,范围为 00 到 109+610^9+6。

3 3
9 4 9
1 2
1 3

1 1
3 2
3 3
27 4 3
999988451 419872 385168
405 12 1

样例解释

第二个查询的路径是 3,1,23,1,2。向量依次为 (405,12,1)(405,12,1)、(27,4,3)(27,4,3)、(324,8,1)(324,8,1)。先叉乘前两个向量,再与第三个叉乘,得到 (−11556,419872,385168)(-11556,419872,385168),取非负余数后得到样例的第二行。

数据范围

1≤n,m≤1051\le n,m\le10^5,1≤Ai≤106+11\le A_i\le10^6+1,1≤x,y≤n1\le x,y\le n。原题标出的权值上限为 10610^6,本题库部分测试中有 106+110^6+1。