【ybt金牌导航5-2-5】【UOJ#33-UR #2】树上GCD

题目描述

给定一棵 $n$ 个节点的树，每个节点有一个权值 $a_i$，定义 $gcd(x,y)$ 表示 $x$ 和 $y$ 的最大公约数，定义 $f(u,v)$ 表示从节点 $u$ 到节点 $v$ 的路径上所有节点的权值的 $gcd$ 值，现在有 $m$ 次询问，每次询问给定两个节点 $u$ 和 $v$，求 $f(u,v)$。

输入格式

第一行包含一个整数 $n$，表示树的节点数。

第二行包含 $n$ 个整数，表示每个节点的权值。

接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示树上存在一条从节点 $u$ 到节点 $v$ 的边。

接下来一行包含一个整数 $m$，表示询问次数。

接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$，表示一次询问。

输出格式

对于每个询问，输出一行一个整数，表示 $f(u,v)$。

数据范围

$1\leq n,m\leq 10^5$,

$1\leq a_i\leq 10^6$

输入样例

5

2 4 6 8 10

1 2

1 3

3 4

3 5

3

1 5

2 4

3 5

输出样例

2

2

2

算法1

(树上倍增+欧拉序+ST表) $O(nlogn+qlogn)$

树上倍增求LCA，欧拉序求区间gcd，ST表维护区间最大值

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(树上倍增+欧拉序+线段树) $O(nlogn+qlog^2n)$

时间复杂度

参考文献

C++ 代码