- Luogu4180 【模板】严格次小生成树[BJWC2010]
- Luogu4234 最小差值生成树
- Luogu4822 [BJWC2012]冻结
- Luogu4172 [WC2006]水管局长
- Luogu2173 [ZJOI2012]网络
- Luogu2147 [SDOI2008]洞穴勘测
- Luogu3203 [HNOI2010]弹飞绵羊
- Luogu1501 [国家集训队]Tree II
- Luogu3950 部落冲突
- Luogu1505 [国家集训队]旅游
- Luogu2486 [SDOI2011]染色
- Luogu4546 [THUWC2017]在美妙的数学王国中畅游
- Loj2006 [SCOI2015]小凸玩矩阵
- CF1023F Mobile Phone Network
- BZOJ3691 游行
Luogu4180 【模板】严格次小生成树[BJWC2010]
Link
结论：有至少一棵次小生成树，和最小生成树只有一条边的差异。非严格的次小生成树可以在求出最小生成树之后，枚举未选的边，用它替代覆盖的路径上的最大边即可。但是题目要求严格次小，所以再记录一下路径上的严格次大边，如果枚举到的边不大于最大边，就替代次大边。
直接lca+倍增就行。用LCT也是可以的。不过LCT常数极大，加了暗黑优化才过kk。
Luogu4234 最小差值生成树
把边从大到小排序。每次枚举一条边，如果两端点未联通，就直接加上。
如果已联通，肯定是贪心地把覆盖路径上最小的边给替换掉。因为从小到大枚举，所以最大边是枚举的这条边，最小边用一个全局指针维护。如果当前已经是一棵生成树（开个变量记录加入的边数即可），就可以用最大边减去最小边了更新答案。
注意LCT维护边的信息是通过化边成点的方式。即新增一个点，夹在两端点之间，点权是原边权。
Luogu4822 [BJWC2012]冻结
分层图最短路。单独一层边权不变，上下两层用原边权的二分之一连接。统计答案时在各层第n个点代价中取min。理性分析一下，层与层之间的边对应的原边（可以减少代价的边）在全图中不会用超过一次。
Luogu4172 [WC2006]水管局长
题目要求动态维护最小生成树。但是有删边操作，这就很不好处理。考虑倒着处理询问，原来的删边变成了加边，就很好维护了。
Luogu2173 [ZJOI2012]网络
开C棵LCT，分别维护各自颜色的森林就行了。操作都是LCT的基本操作。
Luogu2147 [SDOI2008]洞穴勘测
LCT维护联通性。
Luogu3203 [HNOI2010]弹飞绵羊
第(i)个装置和第(i+k_i)个装置连接一条边（第(i+k_i)做父亲）。LCT维护的是一个森林。这样查询就是到根节点路径长度。直接(access(x)，splay(x))，输出(x)的(size)。
Luogu1501 [国家集训队]Tree II
维护乘法和加法，可以借鉴Luogu3373 【模板】线段树 2的方法。
inline void pushmul(int x,int c){times(s[x],c),times(mul[x],c),times(v[x],c),times(pls[x],c);}
inline void pushpls(int x,int c){add(s[x],1ll*siz[x]*c%mod),add(v[x],c),add(pls[x],c);}
inline void pushdown(int x){
if(r[x])pushr(ch[x][0]),pushr(ch[x][1]),r[x]=0;
if(mul[x]^1)pushmul(ch[x][0],mul[x]),pushmul(ch[x][1],mul[x]),mul[x]=1;
if(pls[x])pushpls(ch[x][0],pls[x]),pushpls(ch[x][1],pls[x]),pls[x]=0;
}
pushdown时先乘后加。区间乘包括加法标记都要乘上。因为是LCT维护，所以区间加的时候还要知道子树大小siz[x]。pushup还需要用到单点值v[x]。
Luogu3950 部落冲突
Link
LCT维护联通性。
Luogu1505 [国家集训队]旅游
为什么题单里面全是水题板子题啊，我都要做吐了。
不过这道题有个坑的是要记得初始化，因为他既询问min又询问max。而且初始化要从0开始！！！！然后pushup也要判断是不是边拆成的虚点。不是就不能用(v[x])更新。
Luogu2486 [SDOI2011]染色
(LCT)板子题。(splay)上每个点的子树是原树的一条链，整个(splay)就是整条实链。所以可以记(L[],R[])表示链首和链尾的颜色，(tot)表示颜色段数，合并时讨论一下左右儿子的情况。
inline void pushup(int x){
L[x]=ch[x][0]?L[ch[x][0]]:c[x];R[x]=ch[x][1]?R[ch[x][1]]:c[x];
if(ch[x][0]&&ch[x][1])s[x]=s[ch[x][0]]+s[ch[x][1]]+1-(c[x]==R[ch[x][0]])-(c[x]==L[ch[x][1]]);
else if(ch[x][0])s[x]=s[ch[x][0]]+1-(c[x]==R[ch[x][0]]);
else if(ch[x][1])s[x]=s[ch[x][1]]+1-(c[x]==L[ch[x][1]]);
else s[x]=1;
}
Luogu4546 [THUWC2017]在美妙的数学王国中畅游
就是(LCT)维护点权和。只是普通的是直接读入点权，这个要泰勒展开一下，然后维护各项系数和。直接带(x_0=0)很方便。考虑精度问题函数取12项就够了。
Loj2006 [SCOI2015]小凸玩矩阵
显然二分。但是第(k)大不好做，转化成第(n-k+1)小。所以就变成了判断能否找到(n-k+1)个小于(mid)的值行列都不同。将矩阵上不超过(mid)的点看做1，跑最大匹配。
套路地建图：每行每列建虚点，行和(s)相连，列和(t)相连，矩阵上((i,j))有点就把行(i)和列(j)连接。边容量都是1。
CF1023F Mobile Phone Network
先强制我的边都在最小生成树上，这样构造出一棵最小生成树。对于对手不在生成树上的边，其覆盖的路径上每一条边都要小于等于它的边权，所以是个链上取(min)的操作。
考虑具体做法。因为是取(min)，如果把操作序列按边权从小到大排列，那就变成了区间覆盖问题。如果树上某条边已经被覆盖过了，以后就不会再覆盖。所以可以用并查集维护每个点向上已经覆盖到何处，每次直接在并查集暴跳即可。因为每条边只会被覆盖一次，所以复杂度是( ext O(n))的。
还有一种倍增的做法。对于每条边，他覆盖的((x,y))的链分成((x,lca))和((y,lca))，按照平时倍增的思路步子从大到小跳，进行取min操作。然后全部做完更新答案时，将平时倍增的更新反着做一遍。
for(int j=6;j>=0;--j)
for(int i=1;i<=n;++i)
Min(mn[i][j],mn[i][j+1]),Min(mn[fa[i][j]][j],mn[i][j+1]);
BZOJ3691 游行
将两个限制转化一下，成环或把两个联通块连接，减少的代价都是(C)。
因为(C)是变化的，就先考虑计算没有(C)的部分。
没有(C)的部分是一个最小可重路径覆盖。(Floyd)求出任意两点之间最短路径，转化成最小不重路径覆盖就可以直接做了。
考虑到费用流每次增广花费是递增的，所以每次询问我们可以二分找到一个时间点(p)，在他之前的增广都小于等于(C)，之后的都大于(C)。(p)之前的用增广的费用，之后直接用((n-p)*C)补上。