题意：一棵带边权的树，边权可单边修改，问初始时和每次修改后有多少条路径$\gcd=1$
首先考虑用反演求答案，设$f(n)$为路径$\gcd=n$的路径条数，$g(n)$为路径$\gcd$是$n$倍数的路径条数，那么$g(n)=\sum\limits_{n|d}f(d)$，所以$f(n)=\sum\limits_{d|n}\mu\left(\frac dn\right)g(d)$，答案就是$f(1)=\sum\limits_{d}\mu(d)g(d)$
我们现在要求$g(d)$，先考虑没有修改怎么做，我们对每个$d$预处理出是$d$倍数的那些边（这里可以直接枚举边权的约数，因为边权$\leq10^6$）用这些边构图，答案就是每个连通块的$\binom{siz}2$之和，这里可以用并查集做
加上修改就只预处理那些不被修改的边，先用这些不被修改的边建并查集，每次对第$i$个询问，修改第$1\cdots i$条边的边权后再把这至多$q$条边插进并查集中，再统计答案
总时间复杂度貌似是$O(wq^2\log n)$？？？但是加一些小优化好像可以过...
#include<stdio.h>
#include<vector>
using namespace std;
typedef long long ll;
const int T=1000000;
int pr[T+10],mu[T+10];
bool np[T+10];
void sieve(){
int i,j,M=0;
mu[1]=1;
for(i=2;i<=T;i++){
if(!np[i]){
pr[++M]=i;
mu[i]=-1;
}
for(j=1;j<=M&&i*pr[j]<=T;j++){
np[i*pr[j]]=1;
if(i%pr[j]==0)break;
mu[i*pr[j]]=-mu[i];
}
}
}
struct edge{
int x,y,w;
}E[100010];
struct ask{
int i,v;
}Q[110];
bool del[100010],us[T+10];
vector<int>G[T+10];
ll C;
int fa[100010],dep[100010],siz[100010],M;
struct oper{
int u,f,d,s;
oper(int _u=0,int _f=0,int _d=0,int _s=0){u=_u;f=_f;d=_d;s=_s;}
}stk[200010];
void add(int u){
stk[++M]=oper(u,fa[u],dep[u],siz[u]);
}
int get(int x){
while(x!=fa[x])x=fa[x];
return x;
}
void merge(int x,int y){
x=get(x);
y=get(y);
if(x==y)return;
if(dep[x]<dep[y])swap(x,y);
add(x);
add(y);
fa[y]=x;
if(dep[x]==dep[y])dep[x]++;
C+=(ll)siz[x]*siz[y];
siz[x]+=siz[y];
}
void roll(){
int u=stk[M].u;
fa[u]=stk[M].f;
dep[u]=stk[M].d;
siz[u]=stk[M].s;
M--;
}
ll ans[110];
int val[100010];
int main(){
int n,q,i,j,k,tM;
ll tC;
sieve();
scanf("%d",&n);
for(i=1;i<n;i++)scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].w);
scanf("%d",&q);
for(i=1;i<=q;i++){
scanf("%d%d",&Q[i].i,&Q[i].v);
del[Q[i].i]=1;
}
for(i=1;i<n;i++){
if(!del[i]){
for(j=1;j*j<=E[i].w;j++){
if(E[i].w%j==0){
G[j].push_back(i);
if(j*j!=E[i].w)G[E[i].w/j].push_back(i);
}
}
}else{
for(j=1;j*j<=E[i].w;j++){
if(E[i].w%j==0)us[j]=us[E[i].w/j]=1;
}
}
}
for(i=1;i<=q;i++){
for(j=1;j*j<=Q[i].v;j++){
if(Q[i].v%j==0)us[j]=us[Q[i].v/j]=1;
}
}
for(i=1;i<=n;i++){
fa[i]=i;
dep[i]=1;
siz[i]=1;
}
for(i=1;i<=T;i++){
if(mu[i]&&!(G[i].empty()&&!us[i])){
C=0;
M=0;
for(int j:G[i])merge(E[j].x,E[j].y);
tM=M;
tC=C;
for(j=1;j<=q;j++)val[Q[j].i]=E[Q[j].i].w;
for(j=0;j<=q;j++){
val[Q[j].i]=Q[j].v;
C=tC;
if(us[i]){
for(k=1;k<=q;k++){
if(val[Q[k].i]%i==0)merge(E[Q[k].i].x,E[Q[k].i].y);
}
}
ans[j]+=mu[i]*C;
while(M>tM)roll();
}
while(M)roll();
}
}
for(i=0;i<=q;i++)printf("%lld\n",ans[i]);
}