#HDR002D. Call of The Void

    ID: 195 Type: Default 500ms 128MiB Tried: 32 Accepted: 4 Difficulty: 9 Uploaded By: Tags>数学图论虚树数论欧拉函数其他

Call of The Void

题目背景

youtube官方动画 TEAM_190搬运

又一次,sans 倒在了那把红刀之下。

*真的就没有办法阻止这场屠杀吗?

玩家再次重启了世界,没有人记得自己曾经被杀死过,没有人记得自己在钟声敲响时干了什么。

sans 再次在雪镇游走,等待着玩家的再次到来。不过,他在等待的时候,遇到了一扇以前从来没有见过的门。

他很好奇门里有什么,推开了门,看见里面有一个身影。那个身影用手说道:

*【链接已屏蔽】

sans 想了想,接受了那个身影的邀请。

那个身影站了起来,带着 sans 走到了一个阴暗而又潮湿的地方。

sans 想了起来,这个阴暗而潮湿的地方,是 Alphys 的实验室!

那么这个身影,就是。。。

那个身影走到了控制台前,需要输入密码。不过那个身影表示他记不起密码了。

sans 走了过来,利用时间线轻松地解决了控制台的密码。

此时,sans 看见前方的门打开了。走进去后看见了一台巨大的机器。那个身影告诉了 sans 他的计划。

于是,他们在实验室等待着玩家的到来。不过,这次 sans 将会充满决心。

......

战胜了玩家后,sans 利用决心的力量和 Asgore 的七个灵魂回到了地表。它们很高兴能够再次看见天空中正在下落的太阳。

当 sans 再次回想起那次的遭遇时,很想知道,他利用时间线轻松破解的密码,原本应该如何破解。

题目描述

控制台会给你一颗节点数量为 n n 的树,第 i i 个点的点权为 ai a_i

定义 dis(u,v) dis(u,v) u u v v 的路径上所有点的点权之积。

再定义函数 g g 满足:

g(n)=(d2nμ(nd2))×φ(n)g(n)=(\sum_{d^2|n}\mu(\frac n {d^2})) \times \varphi(n)

控制台的密码为 i=1nj=i+1ng(dis(i,j)) \prod_{i=1}^n\prod_{j=i+1}^ng(dis(i,j))

输入格式

第一行一个数 n n

接下来 n1 n-1 行,每行两个数 u,v u,v ,代表 u u v v 之间有一条边连接。

再接下来一行一共 n n 数,第 i i 个数即为 ai a_i

输出格式

一行,控制台的密码。由于结果可能太大,你只需要输出其对 998244353 998244353 取模的结果即可。

4
1 2
1 3
2 4
8 6 10 5
511705067

提示说明

本题采用捆绑测试。

  • Subtask1(3pts)1n10,1i=1nai1018 1 \leq n \leq 10,1 \leq \prod_{i=1}^n a_i \leq 10^{18}
  • Subtask2(7pts)存在一个 p p ,使得对于每一个 i i 存在一个 ki k_i 满足 ai=pki a_i=p^{k_i}
  • Subtask3(13pts)给出的数为一条链。
  • Subtask4(14pts)存在一个度数为 n1 n-1 的节点。
  • Subtask5(15pts)1n100 1 \leq n \leq 100
  • Subtask6(18pts)1n1000 1 \leq n \leq 1000
  • Subtask7(40pts)无特殊限制。

对于所有数据满足:1n105,1ai106 1 \leq n \leq 10^5,1 \leq a_i \leq 10^6