A
大家使用了整体二分+可撤销并查集，倍增等方法...
考虑线段树合并。
在跑 Kruskal 时，如果一个询问的两个点在同一个连通块内，那么这个询问就是可回答的，但是可回答不一定要回答，因为如果此后加的边权相同那么其实里面的点还能再往外走。
所以在加边时如果新加的边权大于连通块边权，那么回答连通块内未回答的可回答询问。最后把整个连通块回答了。
然后线段树合并维护每个连通块内包含每个询问的多少个点，回答完询问后就把点数置零。记一下区间 max，回答时只走 max = 2 的子树。
B
最大公约数我们都做烂了，今天我们来做一个最小公倍数的题目。
考虑用被我们做烂的最大公约数做。
\[\sum_{i = 1}^n\sum_{j = 1}^n\operatorname{lcm}(A_i, A_j) =\sum_{i = 1}^n\sum_{j=1}^n\frac{A_i A_j}{\gcd(A_i, A_j)} \]那么套路的，记 \(f_x\) 表示最大公约数为 \(x\) 的点对的乘积之和，先算含有公约数 \(x\) 的点对乘积之和，然后减去 \(\sum\limits_{k\ge 2}f_{kx}\)。
然后含有公约数 \(x\) 的点对乘积之和直接算含有约数 \(x\) 的数之和平方就是了。
最后答案是 \(\displaystyle\sum_{i} \frac{f_i}{i}\)。
时间复杂度 \(O(n\sqrt{V})\)，瓶颈在找因数。PC 说这个可以先 \(O(V \ln V)\) 调和级数预处理。
AT：答案减去主对角线在除以 2。
C
考虑比线段树优化建图高级的主席树优化建图。
把题目里连边看作 \(dep\) 小于指定值的 \(dfs\) 序在某一区间（子树）所有点，那么主席树第 \(i\) 棵树就是维护所有 \(dep \le i\) 的点的入树。
建完图跑 Tarjan。
标签：24,连通,询问,sum,回答,24.10,最大公约数,边权 From： https://www.cnblogs.com/KinNa-Sky/p/18499985