虚树学习笔记
概述
比如有这样一个问题: ([SDOI2011]消耗战)
你有一棵树, 1 为根, 有边权,
然后有 m 次询问, 每次给出 k 个点, 求这 k 个点都与 1 不想连, 最少需要断的边权和是多少?
注意 m 可能很大, 但是 \(\sum k \le 5e5\)
于是需要尽量只用询问的这些点,
虚树就是这样一种只包含必要的询问的点和 lca , 以及压缩后的信息(边权)的树
构建虚树需要多少节点
上述已经提到, 尽量只用询问点有保留所需要的信息, 不难想到还要留下 lca ,
所以第一个问题是总共会留下多少的点?
若两个询问点为祖孙关系, 则只用保留祖先
这里设查询点的数量为 \(k\), 考虑极端情况:
1.没有某个是另一个的祖先的情况(不然更少)
2.二叉树(多叉树更少)
那么搞一棵完全二叉树, 然后 k 都放在叶子上, 这样最多 \(2k\)
那么对于所有的询问构建一棵虚树的复杂度就是 \(O(\sum k)\) 了, 非常优越
如何构建虚树
考虑先求出 DFS 序, 并对这次的询问点按照 DFS 序排序
然后依次处理每条根到询问点的树链的构建, 因为虚树中的边就是在这些链上连接的
具体是这样:
- 用栈记录根到当前点的链上保留的点
- 考虑新加入一个点 p, p 与栈顶的点 x(当前链的最深点)有如下关系:
- x 是 p 的祖先, p 不用保留了
- 否则, x 就是这条链的终点了, p 在另一棵子数上, 此时完成 x 链的构建仍需几个步骤:
- 设 x 的上一个元素是 y, 考虑 y 与 x, p 的 LCA 的关系
- 若 y 是 LCA 的祖先，即 y->LCA->x , 显然 LCA 只会产生这两条边
- 若 LCA 是 y 的祖先(或 lca = y), 即 ?->LCA->?->y->x , 那么只能确定这部分, 接下来继续考虑 y 前一个点, 重复 1~3 的步骤, 最后 p 成了将要处理的新的链
- 处理完了 p 点, 回到 2 步骤继续处理下一个
这个思路应该是简单的, 但是细节比较多, 然后对于不同的题, 边权之类的信息又要另外考虑了,
步骤二的具体实现如下:
for (int i = 1; i <= n; ++ i) a[i] = in();
sort(a + 1, a + n + 1, cmp);
stk[top = 1] = 1;
for (int i = 1; i <= n; ++ i)
{
if (a[i] == 1) continue;
if (top == 1) { stk[++ top] = a[i]; continue; }
int lca = LCA(a[i], stk[top]) ;
if (stk[top] == lca) continue;
while (top > 1 && dep[lca] <= dep[stk[top - 1]])
{
addedge(stk[top - 1], stk[top]);
-- top;
}
if (lca != stk[top]) addedge(lca, stk[top]), stk[top] = lca;
stk[++ top] = a[i];
}
for (int i = 1; i < top; ++ i) addedge(stk[i], stk[i + 1]);#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
LL inline in()
{
LL x = 0, flag = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') flag = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
return x * flag;
}
int n, m;
const int MAXN = 25e4 + 10;
int head[MAXN], nume;
struct Adj { int nex, to, w; } adj[MAXN << 1];
void addedge(int from, int to, int w)
{
adj[++ nume] = (Adj) { head[from], to, w };
head[from] = nume;
}
void link(int u, int v, int w)
{
addedge(u, v, w);
addedge(v, u, w);
}
int idx, dfn[MAXN], dep[MAXN], lg[MAXN];
LL mn[MAXN];
int up[19][MAXN];
void DFS(int u, int fa)
{
dfn[u] = ++ idx;
dep[u] = dep[fa] + 1;
up[0][u] = fa;
for (int i = 1; (1 << i) <= dep[u]; ++ i)
up[i][u] = up[i - 1][up[i - 1][u]];
for (int i = head[u]; i; i = adj[i].nex)
{
int v = adj[i].to;
if (v == fa) continue;
mn[v] = min(mn[u], 1ll * adj[i].w);
DFS(v, u);
}
}
int LCA(int x, int y)
{
if (dep[x] > dep[y]) swap(x, y);
while (dep[y] > dep[x])
y = up[ lg[dep[y] - dep[x]] ][y];
if (x == y) return x;
for (int i = 18; i >= 0; -- i)
if (up[i][x] != up[i][y])
x = up[i][x], y = up[i][y];
return up[0][x];
}
namespace solve
{
int head[MAXN], nume;
struct Adj { int nex, to; } adj[MAXN];
void addedge(int from, int to)
{
adj[++ nume] = (Adj) { head[from], to };
head[from] = nume;
}
int n, a[MAXN];
int stk[MAXN], top;
bool cmp(int x, int y) { return dfn[x] < dfn[y]; }
LL DP(int u)
{
LL ret = 0;
for (int i = head[u]; i; i = adj[i].nex)
{
int v = adj[i].to;
ret += DP(v);
}
head[u] = 0;
return !ret ? mn[u] : min(ret, 1ll * mn[u]);
}
void solve()
{
nume = 0;
n = in();
for (int i = 1; i <= n; ++ i) a[i] = in();
sort(a + 1, a + n + 1, cmp);
stk[top = 1] = 1;
for (int i = 1; i <= n; ++ i)
{
if (a[i] == 1) continue;
if (top == 1) { stk[++ top] = a[i]; continue; }
int lca = LCA(a[i], stk[top]) ;
if (stk[top] == lca) continue;
while (top > 1 && dep[lca] <= dep[stk[top - 1]])
{
addedge(stk[top - 1], stk[top]);
-- top;
}
if (lca != stk[top]) addedge(lca, stk[top]), stk[top] = lca;
stk[++ top] = a[i];
}
for (int i = 1; i < top; ++ i) addedge(stk[i], stk[i + 1]);
printf("%lld\n", DP(1));
}
}
int main()
{
n = in();
for (int i = 1; i < n; ++ i)
{
int u = in(), v = in(), w = in();
link(u, v, w);
}
for (int i = 1; i <= n; ++ i) lg[i] = lg[i - 1] + ((2 << lg[i - 1]) == i);
mn[1] = 1e11;
DFS(1, 0);
m = in();
while (m --)
{
solve::solve();
}
return 0;
}
/*
1945
*/