https://www.luogu.org/blog/Miracevin/shuo-ju-jie-gou
一种离线处理方法
可以处理“具体哪个修改对询问有影响”、可以贡献不独立、可以支持插入删除
例题 7
? 给出一张图
? 对每个点求出强制这个点点度为 1 的最小生成树的权值
? ?? ≤ 100000, ?? ≤ 300000
每个边存在三段:[1,x-1],[x+1,y-1][y+1,n]
LCT维护最小生成树
i的答案再加上和i相邻的边权最小值
例题 8
? 给一棵树，边有边权
? 每次操作是删除一条边并加入一条边，保证操作完还是树
? 你需要维护有多少点对 ??, ?? 的路径上所有数的最大公约数是 1
? ?? ≤ 100000, ???? ≤ 100000, ?? ≤ 30000
反演一下得到：
ans=∑miu(d)f(d)
f(d)表示路径上的点都是d的倍数的点对的个数
也就是，所有是d的倍数的点构成的若干个联通块，f(d)=∑szi*(szi-1)/2
考虑对每个边出现的区间进行线段树分治
然后dfs，用按秩合并并查集维护每个d的f(d)，也就是维护好联通块∑szi*(szi-1)/2
每加入一个边，枚举这个边两边的点的gcd的约数d，再对每个并查集进行维护。
栈序撤销
（当然LCT也可以，常数爆炸就是了）
例题 9
? （CTSC2016）
? 你需要维护若干个版本的集合，每个集合元素是 ??, ??
? 每次可以扩展一个版本，扩展内容为加一个新元素或删除一个已
有元素
? 每次询问一个 ??，要你在给定版本 ?? 的集合中找出 ??, ?? 使得
?? ? ?? 2 + ?? 最小
? ??, ?? ≤ 1000000
原文：https://www.cnblogs.com/Miracevin/p/10355084.html