热身 [ABC359G] Sum of Tree Distance

【题意】

给定一个 $N$ 个节点的树，每个节点有一个颜色 $A_i$,询问所有颜色相同的点之间的距离和。

$2 \le N \le 2 \times 10^5, A_i \le N$

【分析】

首先，考虑暴力。 枚举每一种颜色，计算每条边走几次，对于颜色 $A_i$: $size[x]$ 表示以点 $x$ 为根的子树中 $A_i$ 颜色的个数，那么边 $(x,y)$走的次数就是 $(n-size[y])*size[y]$，求出 每条边走的次数*边权 之和就是答案。 时间复杂度：$O(N^2)$

考虑优化,如果在原树上计算 $size[x]$ , $dfs$ 一遍就是 $O(N)$,考虑到各种颜色点总个数是 $n$, 那么可以建立一颗“瘦身版”的树，这种树不改变目标点之间的上级关系，忽略非目标点，大大提高效率，这种“瘦身版”的树就是虚树。接下来我们分析如何建立虚树。

---

虚树

针对一颗大树，多次询问目标点数量总和数量有一个上限的情况下，往往考虑建立虚树。

虚树本质就是将原来大树，浓缩为**“瘦身版”的小树**。

虚树具有以下特点：

1. 不改变目标点之间的上下级关系，只建立目标点与他们之间最近公共祖先。
2. 构成虚树的点（关键点）=目标点 + 两两之间的最近公共祖先 + 树根。
3. 虚树做了“瘦身”，保留了原树的“骨架”。
4. 大小：目标点如果为 $k$，那么构成虚树的点（关键点）不超过 $2*k$ 。 例如：如果满二叉树的所有叶子节点都是目标点，虚树就是原树。

往往为了解决一类树上DP问题，往往给出多组查询点（目标点），但查询点总数有限，考虑构建“瘦身”版虚树，从而降低复杂度。这种问题的套路：树上LCA + 虚树 + 树上DP

如何创建虚树

基本过程如下：

1. 预处理原树 $dfs$ 序和 $lca$，用单调栈维护关键点。（单调栈中只存放根到当前点的链上的点）

2. 对 $k$ 个关键点按 $dfs$ 序排序，根节点入栈。

3. 对于点 $a[i]$ ，查询栈顶与 $a[i]$ 的 $lca$ ，若 $lca=getlca(st[top],a[i])$ ,进行分类讨论：

   (1) $lca=st[top]$ 即 $a[i]$ 是 $st[top]$ 子树内的节点，直接将 $a[i]$ 入栈

   (2) $lca!=st[top]$ 即 $a[i]$ 不是 $st[top]$ 子树内的节点（如上图） 此时 $lca$ 下面路径上的关键点都应该出栈，出栈时从 $st[top-1]$ 到 $st[top]$ 连边.

   注意：当 $dep[st[top-1]]<dep[lca]$ 时停止出栈。

   此时

   (1) $lca=st[top]$, $a[i]$ 直接入栈

   (2) $lca!=st[top]$, $lca$ 与 $st[top]$ 连边，将$st[top]$ 替换为 $lca$ ,之后 $a[i]$ 入栈。

4. 最后将栈中的关键点依次出栈，连接 $st[top-1]$ 与 $st[top]$ 的边。

建立虚树参考代码：

void build() //建虚树
{ 
	sort(a+1,a+k+1,cmp);//按dfs序排序
	tot=0;//清空
	s[top=1]=1;//根节点入栈
	if(a[1]!=1)s[++top]=a[1];  //使得虚树的根节点还是1 
	for(int i=2;i<=k;i++){ //枚举查询点
		int lca=getlca(s[top],a[i]);	
		// 对当前链连边,top出栈
		while(top>1 && dep[s[top-1]]>=dep[lca])
			add(s[top-1],s[top]),top--; 
			//对lca和top连边,top出栈,lca入栈
		if(lca!=s[top])add(lca,s[top]),s[top]=lca;
		// 查询点入栈
		s[++top]=a[i];
	}
	while(top)//对最后一条链连边,top出栈
		add(s[top-1],s[top])，top--;
}

CF613D Kingdom and its Cities

【题意】

给定一颗有 $n$ 个点的树，有 $q$ 组询问，每组询问给定 $k$ 个点，你可以删掉不同于这 $k$ 个点的一些点，使得这 $k$ 个点两两不联通，求最少删除多少点，如果不可能输出 $-1$ ，询问之间独立。

$n \le 10^5 ,q \le 10^5, \sum k \le 10^5$

【分析】

如果在原树上暴力 $DFS$ ,时间复杂度为 $O(nq)$ 注意到 $\sum k \le 10^5$ ,查询点总数有限，我们每次把 $k$ 个查询点分离出来，重构一颗规模较小的虚树，时间复杂度降为 $O(∑k)$ 在虚树上，$s[x]$ 表示以 $x$ 为根的子树中是否有查新点 如果 $x$ 是查询点，如果 $y$ 也是查询点，那么就必须删掉$(x->y)$ 上的一个点，$ans++$ .

如果 $x$ 不是查询点，如果子树有 $2$ 个以上有标记，那么 $ans++$ 。如果子树至少 $1$ 个有标记，此时将 $x$ 标记。 注意多次询问，需要清空虚树，同时 size 数组也需要清空，但不能使用 memset .

P2495[SDOI2011] 消耗战

【题意】

给定一颗有 $n$ 个点的有边权的树，$m$ 次询问，每次给定 $k$ 个点，请选择断开若干条边，是得 $k$ 个点不能到达根节点，求出断开边总代价的最小值。

$n \le 2.5 \times 10^5 , m \le 5 \times 10^5 , ∑k \le 5 \times 10^5$

【分析】

发现 $∑k ≤ 5 \times 10^5$,想到了建虚树 $root-x-y$ （ $x,y$ 都是目标点）如果是一条链，必须要断开 $x$ ，那么 $y$ 就自动断开了。

那么建虚树，就可以只建 $root - x$ ，创建虚树的时候剪枝就可以了

虚树上DP ,考虑 $x$ 的儿子 $y$：

如果 $y$ 是目标点：$dp[x] = dp[x] + w(x,y)$

如果 $y$ 不是目标点： $dp[x] = ∑ min(dp[y],w(x,y))$

虚树练习题

1.「HEOI2014」大工程

2.「HNOI2014」世界树

3.Luogu P4242 树上的毒瘤

4.Luogu P7409 SvT（CF1073G）