Skip to content

14216: 【原4216】树上GCD

题目

题目描述

author: Peiming Yang 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4216

Description

给你一个有\(n\)个节点的树,树上的每个节点都有两个点权\(a_i\)和\(b_i\),求

\(\prod_{i=1}^n \prod_{j=i}^n max(1, f(i,j)*min(1,g(i,j)))\)

设S(i,j)是i到j路径上所有点的集合,

\(f(i,j) = gcd(a_x), x \in S(i,j)\)

\(g(i,j) = \Sigma_{x \in S(i,j)} b_x\)

Input Format

第一行有一个整数\(n\),代表树的节点数

接下来\(n-1\)行,每行两个整数\(u_i\)和\(v_i\), 表示\(u_i\)和\(v_i\)之间有一条边

接下来一行有\(n\)个整数,分别表示每个节点的\(a_i\),

最后一行有\(n\)个整数,分别表示每个节点的\(b_i\)。

Output Format

最终得到的结果,结果模\(1000000007(1e9+7)\)输出。

Sample Input

8
1 2
1 3
3 4
2 5
5 6
6 7
7 8
10 6 10 10 10 5 1 10 
9 6 2 1 8 2 3 4

Sample Output

999986567

Limit

  • 对于20%的数据,n<=5000

  • 对于另外20%的数据,树是一条链

  • 对于另另外10%的数据,树是随机

  • 对于另另另外10%的数据,树是是菊花状的

  • 对于100%的数据,n<=200000

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!