GCD 和简单路径
GCD and Simple Path
给定 N vertices and N-1 edges 的无向连通图。 ith顶点上写的数字是val[i]。任务是计算满足以下条件的对 (x, y) 的数量：
- 0 ≤ x < y ≤ N-1
- The GCD of the numbers written on the vertices on the simple path in the given graph from x to
y should be divisible by K.
示例：
输入：
N = 4, K = 2
边[] = {{0, 1}, {0, 2}, {2, 3}}
Val[] = {2, 6, 4, 3}
输出：
3
解释：
0 - 1
|
2 - 3
共有三对 - (0,1)、(1,2) 和
(0,2) 满足两个条件。
这里有两个观察结果：
1)它是一个连通图，有n-1条边。所以它必须是一棵树。
2)要使条件2成立，所有写在x和y之间简单路径的节点上的数字必须是k或k的倍数。
根据这两个观察结果，我们可以设计一个解决方案
Replace all val[i]'s with val[i]%k.
Foreach i from 0 to n-1:
a. if val[i]==0, and not visited before Run a dfs from node i.
b. In dfs only visit the nodes for which val[node]=0 and not visited before. Return the number of nodes you visited on this run. Let this number be x. Also mark these nodes visited.
c. Add xC2 = (x*(x-1))/2 to the answer. (Why? because all the pairs of these visited nodes satisfies both of our conditions. We can select 2 nodes in xC2 ways.).
给定 N vertices and N-1 edges 的无向连通图。 ith顶点上写的数字是val[i]。任务是计算满足以下条件的对 (x, y) 的数量：
- 0 ≤ x < y ≤ N-1
- The GCD of the numbers written on the vertices on the simple path in the given graph from x to y should be divisible by K.
示例：
输入：
N = 4, K = 2
边[] = {{0, 1}, {0, 2}, {2, 3}}
Val[] = {2, 6, 4, 3}
输出：
3
解释：
0 - 1
|
2 - 3
共有三对 - (0,1)、(1,2) 和
(0,2) 满足两个条件。
这里有两个观察结果：
1)它是一个连通图，有n-1条边。所以它必须是一棵树。
2)要使条件2成立，所有写在x和y之间简单路径的节点上的数字必须是k或k的倍数。
根据这两个观察结果，我们可以设计一个解决方案
Replace all val[i]'s with val[i]%k.
Foreach i from 0 to n-1:
a. if val[i]==0, and not visited before Run a dfs from node i.
b. In dfs only visit the nodes for which val[node]=0 and not visited before. Return the number of nodes you visited on this run. Let this number be x. Also mark these nodes visited.
c. Add xC2 = (x*(x-1))/2 to the answer. (Why? because all the pairs of these visited nodes satisfies both of our conditions. We can select 2 nodes in xC2 ways.).