虚树学习笔记

这玩意怎么变成 8 级了/ll

SDOI2020

problem

给定一颗 $n$ 个节点的树，每个边删掉后都有 $a_i$ 的代价。一共 $m$ 次询问，每次给定 $k$ 个关键点，求使得 $1$ 号节点和所有关键点都不连通的最小代价。$n \le 2.5 \times 10^5 ,m \le 5 \times 10^5, \sum k \le 5\times 10^5$ 。

暴力 DP

首先看到这个问题第一眼，我们都会一个 DP 。每个询问单独考虑，记 $dp_i$ 为 $i$ 不与 $i$ 子树内的任意关键点联通的最小代价，DP 的过程也很简单，枚举 $i$ 的每个儿子 $j$ ，记 $i,j$ 之间的边权为 $w_{i,j}$ ，那么有：

• 若 $j$ 是关键点，那么 $dp_i = dp_i + w _ {i,j}$ 。
• 否则，$dp_i = dp_i + \min (w_{i,j},dp _j)$ 。

最后 $dp_1$ 就是答案。这样的 DP 时间复杂度是 $O(nm)$ 的，考虑优化。

建树

首先，我们猜测只有这三类点是有用的：

1. 根
2. 关键点
3. 任意两个关键点的 LCA

前两者很好理解，这里证明一下第三者。

首先，一个关键点会将信息传递给自己到根的路径上的所有点。那么一点会与有 $x$ 条路径经过的儿子的 $dp$ 值不同，当且仅当其是某大于等于 $x+1$ 条路径的交点。那么除了根和关键点以外只有两个关键点的 LCA 有贡献。

于是，我们就可以把原来树上的无用点的信息都压到有用点上的，这样缩成的一颗节点较少的树就叫做 虚树 ,在虚树上进行操作。

对于这道题，我们很容易想到可以枚举每一对关键点，然后求出其 LCA 并建树，但是这样的复杂度是 $O(k^2 \log n)$ ，极端情况下甚至比朴素 DP 还要糟糕，那么我们就需要更快的建树方式。

之所以枚举的复杂度为 $O(k^2\log n)$ ，是因为在枚举 $\{a_1,a_2\}$ 时，会出现大量重复的 $\text{lca}(a_1,a_2)$。

我们建立点集 $A$ ，并把所有键点和 $1$ 加入 $A$ 。接着将关键点按 DFS 序排序，再遍历关键点序列，把相邻两点 $x$ 和 $y$ 的 LCA 也加入序列 $A$ 。

由于 DFS 序的特性，此时 $A$ 已包含了所有 虚树上的点 ，接下来只要考虑如何用 $A$ 建树即可。

把 $A$ 再次排序并去重，再遍历一遍 $A$ ，对于相邻点 $x$ 和 $y$ ，连接 $\text{lca}(x,y)$ 和 $y$ ，最终得到的就是虚树。

考虑为什么可以直接连 $\text{lca}(x,y)$ 。

这是因为，对于点 $x$ 和 $y$ ：

• 若 $x$ 是 $y$ 的祖先节点，则 $\text{lca}(x,y)$ 即为 $x$ 。由于 不存在 点 $z \in \complement_A{\{x,y\}}$ 的 DFS 序在 $x$ 和 $y$ 之间，故 $x$ 到 $y$ 的路径上 没有 其它 $A$ 中的点，可以直接连。
• 若 $x$ 不是 $y$ 的祖先节点，对于 $\text{lca}(x,y)$ 和 $y$ ，同样 不存在 $z \in \complement_A{\{x,y\}}$ 在 $\text{lca}(x,y)$ 到 $y$ 的路径之间，可以直接连。
  这里我们可以用反证法：若存在 $z \in \complement_A{\{x,y\}}$ 在 $\text{lca}(x,y)$ 到 $y$ 的路径之间，则 $dfn(x)<dfn(z)<dfn(y)$，不满足 $A$ 按 DFS 排序后的性质，故命题得证。

这样，我们就在 $O(k \log n)$ 的时间内建出了一颗虚树，且点的数量级是 $O(k)$ 的。

DP

考虑把原来的那个 DP 丢到虚树上来做。

记 $w_i$ 为在原来的树上， $i$ 到 $1$ 的路径权值最小值， $dp_i$ 为使 $i$ 不与其子树内的点联通的最小代价。

对于每个 $i$ ，枚举其儿子 $j$ ，则有：

• 若 $j$ 是关键点，那么 $dp_i=dp_i + w_j$
• 若 $j$ 不是关键点，那么 $dp_i=dp_i + \min (dp_j,w_j)$

这个也很好理解，因为只需要断开原来树上的边权最小的边就可以了。

$dp_1$ 就是答案。

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+9;
const int INF=1e18;
const int MOD=998244353;
int n;
vector<int> G[maxn];
int m;
unordered_map<int,int> a[maxn];
int w[maxn];
int fa[maxn][30];
int dep[maxn];
int dfn[maxn];
int tot;
void dfs(int u,int f)
{
	dfn[u]=++tot;
	fa[u][0]=f;
	dep[u]=dep[f]+1;
	w[u]=min(a[f][u],w[f]);
	for(int i=1;i<30;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
	for(auto v:G[u]) if(v!=f) dfs(v,u);
}
int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int j=29;j>=0;j--) if(dep[fa[x][j]]>=dep[y]) x=fa[x][j];
	if(x==y) return x;
	for(int j=29;j>=0;j--) if(fa[x][j]!=fa[y][j]) {x=fa[x][j];y=fa[y][j];}
	return fa[x][0];
}
int k;
bool cmp(int x,int y) {return dfn[x]<dfn[y];}
map<int,bool> guan;
vector<int> b;
vector<int> A;
map<int,vector<int>> e;
int dp(int u)
{
	if(guan[u]) return w[u];
	int tmp=0;
	for(auto v:e[u]) tmp+=dp(v);
	return min(tmp,w[u]);
}
void solve()
{
	b.clear(),A.clear();
	guan.clear();
	e.clear();
	cin>>k;
	for(int i=1;i<=k;i++) {int x;cin>>x;guan[x]=1;b.push_back(x);}
	A.push_back(1);
	for(auto v:b) A.push_back(v);
	sort(b.begin(),b.end(),cmp);
	for(int i=0;i<b.size()-1;i++) A.push_back(lca(b[i],b[i+1]));
	sort(A.begin(),A.end(),cmp);
	//cout<<'g';for(auto v:A) cout<<v<<' ';cout<<'g'<<'\n';
	int tot=unique(A.begin(),A.end())-A.begin();
	//cout<<tot<<'\n';
	//cout<<'g';for(auto v:A) cout<<v<<' ';cout<<'g'<<'\n';
	for(int i=0;i<tot-1;i++) e[lca(A[i],A[i+1])].push_back(A[i+1]);
	//for(int i=1;i<=n;i++) for(auto v:e[i]) cout<<i<<' '<<v<<'\n';
	cout<<dp(1)<<'\n';
}
signed main()
{
	//freopen("test.in","r",stdin);
	//freopen("test.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=0;i<=n;i++) w[i]=INF;
	a[0][1]=INF;
	for(int i=1;i<n;i++) 
	{
		int u,v,d;
		cin>>u>>v>>d;
		G[u].push_back(v);G[v].push_back(u);
		a[u][v]=d,a[v][u]=d;
	}
	dfs(1,0);
	//for(int i=1;i<=n;i++) cout<<fa[i][0]<<' ';cout<<'\n';
	//for(int i=1;i<=n;i++) cout<<w[i]<<' ';cout<<'\n';
	cin>>m;
	while(m--) solve();
	return 0;
}