一种很有用的东西。体现了关键点的思想。
应用1
树上每个节点有颜色,问一个子树内有几种颜色。
对每种颜色的点集按 DFS 序排序,点所在位置权值 +1,相邻两个的 LCA 处权值 -1。子树求和即可。
正经的应用
建虚树:
q[hh=0]=1;
for(i){
int l=lca(a[i],q[hh]);
while(hh&&dep[q[hh]]>dep[l]){
if(dep[q[hh-1]]>dep[l]) add(q[hh-1],q[hh]);
else add(l,q[hh]);
--hh;
}
if(q[hh]!=l) q[++hh]=l;
if(l!=a[i]) q[++hh]=a[i];
}
while(hh){
add(q[hh-1],q[hh]);
--hh;
}
最喜欢的一种写法,思路很清晰,特判少。
本质是堆维护当前右链。为了有一个固定的根,可以默认把 \(1\) 放进去。
注意清空虚树时要在 DFS 里面动态删。
结合树形 DP
对树上某些关键点进行修改并询问一些没有修改很好做的东西。这时候可以用虚树结合 DP 处理。
(一些简单DP题)
Plus-对树上不同类型点累计贡献(换根DP)
典型的一个题:颜色路径。
如果固定了一种颜色,求别的颜色到它的距离是容易的,换根DP即可。
这道题询问了非常多次两种颜色之间所有路径的长度和。考虑分类处理。
有一个关键性质是所有颜色的点数和是 \(n\)。所以点数大于 \(\sqrt n\) 的颜色少于 \(\sqrt n\) 种,对于这部分跑虚树,复杂度 \(O(n\sqrt n)\)。
考虑小于的怎么办,一个很“启发式”的想法是对于询问的一对颜色,谁点数多就在谁的虚树上算,这样小于 \(\sqrt n\) 的东西接受的询问也是小于 \(\sqrt n\) 的一些颜色,由于总共 \(Q\) 组询问,所以这部分的复杂度总和是 \(O(Q\sqrt n)\)。
所以这道题最终的复杂度就是 \(n\sqrt n\) 级别的,由于虚树的大常,实际上比正常根号算法跑得慢了许多。
标签:颜色,dep,sqrt,hh,虚树,DP From: https://www.cnblogs.com/mRXxy0o0/p/17973596