网络

内存限制：256 MiB 时间限制：10 Sec

在Star的不懈努力下，终于建成了一个含有N个结点的情报网络。这N个结点通过N - 1条联络边两两相连，每条联

络边有一个特征值w。每当有情报传递时，它必然是在一对点之间展开的（起末点交换视为一种），其传递的途径

为情报网络上的简单路径；也就是说，在N个结点的情报网络中共有C(N, 2)种不同的情报传递途径。对于确定的情

报传递途径，它的特征值为它所经过的每条边的特征值的最大公约数。Star知道，特征值为1的情报传递途径是危

险的，并且在整个网络运转的过程中，会发生Q次某条边特征值改变的情况。他想分别计算出这Q + 1个局面（含初

始局面）中的危险途径个数

第一行一个整数N；

以下N - 1行每行三个整数u、v、w表示在结点u、v之间存在一条特征值为w的边；

接下来一行一个整数Q；

以下Q行每行两个整数k、x，表示将读入的第k条边（下标从1开始）的特征值改为x。

N ≤ 100000，Q ≤ 100，1 ≤ w、x ≤ 10^6

输出Q + 1行，每行一个整数

依次表示初始局面、第1次修改后的局面、第2次修改后的局面……第Q次修改后的局面所对应的危险途径个数。

#5269. 网络