dsu on tree 学习笔记

• 这是一个黑科技，考虑树链剖分后，每个点只会在轻重链之间转化(log)次。
• 考虑暴力是怎么写的，每次枚举一个点，再暴力把子树全部扫一边。
• (dsu on tree.)的思想就是保留重儿子不清空，每次扫一边轻儿子，再把轻儿子的贡献加上。
• 关键代码：

void Dfs2(R i,R fm,R op){
	for(R k=hd[i];k;k=nt[k])
		if(to[k]!=fm&&to[k]!=sn[i])
			Dfs2(to[k],i,0);
	if(sn[i])Dfs2(sn[i],i,1),vis[sn[i]]=1;
	upd(i,fm,1),vis[sn[i]]=0,ans[i]=sum[Mx];
	if(!op)upd(i,fm,-1);
}

• 其中(upd)表示计算子树内部除开(vis)的答案。
• 首先枚举所有的轻儿子把轻儿子答案算出来。
• 注意这个时候是没有加到这个儿子的答案的，因为轻儿子的贡献算完即撤销。
• 然后递归重儿子，算重儿子的答案，这个时候重儿子的答案不会撤销，所以(Dfs)完之后数组内仍然保留了重儿子的信息。
• 然后(upd)，就是重新计算除了重儿子之外别的儿子的贡献。
• 然后更新当前点的答案。
• 最后如果当前点不是重儿子，就把整个子树的所有信息清空，否则保留。
• 复杂度是(O(nlogn))的

烂大街的例题：

• CF600E Lomsat gelral
• 一棵树有n个结点，每个结点都是一种颜色，每个颜色有一个编号，求树中每个子树的最多的颜色编号的和。
• 模板题，维护每个颜色的出现次数和每种次数的颜色编号之和，修改类似于莫队是均摊(O(1))的，实时维护最大值是多少即可。
• 复杂度(O(nlogn))