虚树 学习笔记

又是以前学过的知识......
对于一类特殊的树上问题，虚树通常可以简化树的结构，从而降低时间复杂度。

概念

有这样一类树上数据结构题，每组询问会涉及树中若干个关键点，但所有询问涉及的关键点总数并不多（通常需要输入这些关键点，所以也不可能太多，一般与树的大小同阶）。

对于这样的问题，每次询问我们并不需要知道整棵树的结构信息，而只需要知道关键点之间的结构信息。那么，我们可以考虑建出一棵虚树，只保留关键点间的相对结构。

为了保留相对结构，我们除了要将关键点保留，还需要将它们两两的 LCA 保留，同时虚树中一条边的边权为原树中对应路径的边权和。

可以证明，树上 $k$ 个关键点两两的 LCA 个数不超过 $k-1$，这意味着虚树的节点数是 $\mathcal O(k)$ 的，非常优秀。

构造

与笛卡尔树的构造类似，核心都是用栈维护右链。

考虑按 dfs 序依次将关键点插入虚树，为了方便，我们新增一个超级根指向原来的树根。

一开始栈中只有一个超级根，当要加入点 $u$ 的时候，我们求出 $u$ 与栈顶元素 $v$ 的 LCA（由于超级根的存在，栈不会为空），记为点 $p$。

若 $p = v$，说明 $v$ 是 $u$ 的祖先，因此直接将 $u$ 加入栈，延长右链。

否则说明 $u$ 和 $v$ 在 $p$ 的不同子树中，因此我们要更新右链，注意此时 $p$ 一定在右链中，但不一定在栈中。

所以我们不断退栈并连边，直到栈顶的第二个元素的深度比 $p$ 小，分类讨论一下栈顶和 $p$ 是否为同一个点，然后退栈，加入 $p,u$。

最后将栈中的点连边即可，时间复杂度 $\mathcal O(n \log n) - \mathcal O(k \log k)$。

【模板】

const int N = 2e5 + 7;
int n, m, q, dfn[N], tot, f[N][21], d[N], s[N], t;
vi e[N], g[N];

void dfs(int x) {
	dfn[x] = ++tot;
	for (int y : e[x])
		if (y != f[x][0]) {
			d[y] = d[x] + 1, f[y][0] = x;
			for (int i = 1; f[y][i-1]; i++)
				f[y][i] = f[f[y][i-1]][i-1];
			dfs(y);
		}
}

inline int lca(int x, int y) {
	if (d[x] > d[y]) swap(x, y);
	for (int i = 20; ~i; i--)
		if (d[f[y][i]] >= d[x]) y = f[y][i];
	if (x == y) return x;
	for (int i = 20; ~i; i--)
		if (f[x][i] != f[y][i])
			x = f[x][i], y = f[y][i];
	return f[x][0];
}

inline void virtual_tree(vi &p) {
	sort(p.begin(), p.end(), [](int x, int y) { return dfn[x] < dfn[y]; });
	//p.erase(unique(p.begin(), p.end()), p.end());
	vi q = p;
	for (int x : p) {
		int lca = ::lca(x, s[t]);
		if (lca != s[t]) {
			while (t && d[s[t-1]] >= d[lca])
				g[s[t-1]].pb(s[t]), g[s[t]].pb(s[t-1]), --t;
			if (lca != s[t])
				g[lca].pb(s[t]), g[s[t]].pb(lca), s[t] = lca, q.pb(lca);
		}
		s[++t] = x;
	}
	if (t) while (--t) g[s[t]].pb(s[t+1]), g[s[t+1]].pb(s[t]);
	p = q;
}

int main() {
	rd(n), rd(q);
	for (int i = 1, x, y; i < n; i++)
		rd(x), rd(y), e[x].pb(y), e[y].pb(x);
	d[1] = 1, dfs(1);
	while (q--) {
		rd(m);
		vi a, p;
		for (int i = 1, x; i <= m; i++)
			rd(x), a.pb(x), p.pb(x);
		virtual_tree(p);
		/*
		for (int x : p)
			for (int y : g[x])
				if (x < y) debug("%d %d\n", x, y);
		*/
		// to do
		for (int x : p) g[x].clear();
	}
	return 0;
}

【练习】P3320 [SDOI2015]寻宝游戏

const int N = 1e5 + 7;
int n, m, dfn[N], rnk[N], num, d[N], f[N][21];
bool v[N];
vector<pi> e[N];
ll s[N], ans;
set<int> st;

void dfs(int x, int fa) {
	dfn[x] = ++num, rnk[num] = x, d[x] = d[f[x][0]=fa] + 1;
	for (int j = 1; f[x][j-1]; j++) f[x][j] = f[f[x][j-1]][j-1];
	for (pi o : e[x])
		if (o.fi != fa) s[o.fi] = s[x] + o.se, dfs(o.fi, x);
}

inline int lca(int x, int y) {
	if (d[x] > d[y]) swap(x, y);
	for (int i = 20; ~i; i--)
		if (d[f[y][i]] >= d[x]) y = f[y][i];
	if (x == y) return x;
	for (int i = 20; ~i; i--)
		if (f[x][i] != f[y][i])
			x = f[x][i], y = f[y][i];
	return f[x][0];
}

inline ll S(int x, int y) {
	return s[x] + s[y] - 2 * s[lca(x,y)];
}

int main() {
	rd(n), rd(m);
	for (int i = 1, x, y, z; i < n; i++)
		rd(x), rd(y), rd(z), e[x].pb(mp(y, z)), e[y].pb(mp(x, z));
	dfs(1, 0);
	while (m--) {
		int x;
		rd(x), x = dfn[x];
		if (!v[rnk[x]]) st.insert(x);
		auto it = st.lower_bound(x);
		int y = rnk[it==st.begin()?*--st.end():*--it];
		it = st.upper_bound(x);
		int z = rnk[it==st.end()?*st.begin():*it];
		if (v[rnk[x]]) st.erase(x);
		x = rnk[x];
		ll d = S(x, y) + S(x, z) - S(y, z);
		if (!v[x]) v[x] = 1, ans += d;
		else v[x] = 0, ans -= d;
		print(ans);
	}
	return 0;
}

参考资料

• Sengxian 虚树学习笔记