虚树学习笔记

虚树是对于若干关键点，新建一个 \(\Omicron(k)\) 个节点的树，包含所有节点任意组合的 lca，来在上面跑一些算法，降低复杂度

lca 性质

以下默认树的总节点数为 \(n\)，

1. \(k\) 个节点两两组合的不同 lca 个数最多 \(k-1\) 个
   证明：将所有节点按 dfn 值排序，对于不相邻的两个点 \(x,y, dfn_x < dfn_y\)，设它们的 lca 为 \(p\)。当 \(p = x\) 或 \(p = y\) 时，显然此时仍有 \(x\) 右边或 \(y\) 左边的点 \(u\) 和 \(x\) 或 \(y\) 的 lca 为 p；否则，\(x\) 和 \(y\) 一定在 \(p\) 的子树中，则必存在一点 \(u\)，为 \(x\) 子树内 dfn 值最大的点，那么 \(u\) 和 \(u\) 的下一个点的 lca 一定为 \(p\)

2. \(k\) 个节点，所有节点任意组合的不同 lca 个数最多 \(k-1\) 个
   证明同上

3. \(k\) 个节点，建出虚树后只有一个根节点
   证明：全部节点的 lca 的子树包含了所有 lca

建树

二次排序+lca连边

有了刚才的结论，先按 dfn 排序，然后相邻点对 lca，把所有点丢进去去重，再按 dfn 排序，最后相邻点 \(x,y\) 连 \(LCA(x,y) \rightarrow y\) 的边即可，证明显然

题目

P2495 【模板】虚树 / [SDOI2011] 消耗战

简单树形 DP，注意把 \(1\) 号点加进虚树

P4103 [HEOI2014] 大工程

树形 DP 基本功，维护一些信息即可

CF1320E Treeland and Viruses

考虑病毒传播过程，直接做复杂度明显不对，考虑使用类似 dijkstra 的算法，显然需要记录每个点第几轮被传播的和它本轮还能首先，传播的三个特点保证了我们 dj 时可以直接扩展和取最优。主要代码如下

void dj(){
	priority_queue<Q,vector<Q>,cmpq> q;
	while (q.size()) q.pop();
	F(i,1,k) dis[tmp[i]] = {1e18,1e9}, vis[tmp[i]] = 0;
	F(i,1,k1) q.push({vt1[i],i,sd[i]}), dis[vt1[i]] = {i,sd[i]};
	while (q.size()){
		int u = q.top().u; q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		//cout<<u<<" "<<dis[u].fr<<" "<<dis[u].sc<<"\n";
		for (auto v:go[u]){
			pli du;
			if (dis[u].sc >= D(u,v)){
				du = make_pair(dis[u].fr,dis[u].sc-D(u,v));
			} else {
				int _sd = sd[(dis[u].fr-1)%k1+1];
				int w = (D(u,v)-dis[u].sc+_sd-1)/_sd*k1;
				du = make_pair(dis[u].fr+w,_sd-1-(D(u,v)-dis[u].sc-1)%_sd);
			}
			if (!fg[v] && chk(du,dis[v])){
				dis[v] = du;
				q.push({v,dis[v].fr,dis[v].sc});
			}
		}
	}
}