用途
对于大多数情况，树中只有很少一部分点是对当前要处理的信息是有意义的。
我们可以在保留这些有意义的点，不破原树结构的情况下得到一个很精简的树，这样我们就不用遍历整颗树了。
这种做法就叫虚树。
做法
我们管这些有意义叫关键点，对这些关键点按 dfn 序排序。
考虑构造一个栈，表示当前的维护的琏。
考虑遍历关键点，当前遍历到 $x$ ，则有如下情况
令 $p$ 为 $x$ 和栈顶的 lca。
- 如果 $p$ 是栈顶，直接将 $x$ 加入栈；
- 如果栈中次顶的 dfn $< dfn_p$ ，则证明当前结点和栈顶不在同一条链上，则需加入 $p$ 到栈中。
- 如果不是以上两种情况，弹出栈顶回到步骤 1。
在弹出栈顶的时候连边。
容易发现，令 $k$ 为关键点个数，则总结点个数在 $O(k)$ 中，则构造复杂度在 $O(k \log n)$ 内，如果使用 $O(1)$ LCA，则构造复杂度可以优化到 $O(k)$ 。
例 Luogu P2495 [SDOI2011] 消耗战
题目链接: https://www.luogu.com.cn/problem/P2495
题目大意
给定一个根为 $1$ ，大小为 $n$ 的树。
$q$ 次询问，每次询问给定一些关键点，最小化需要删除的边的边权，使得所有关键点和 $1$ 不联通。
$\sum k \leq 5 \times 10^5, n \leq 2.5 \times 10^5$
做法
首先考虑只有一次询问怎么做。
容易构造 DP：
$$
f(x) = \sum_{y \in son_{x}}
\begin{cases}
e(x,y) & y 是关键点 \\
\min( e(x,y), f(y) ) & y 不是关键点
\end{cases}
$$
发现对于不是关键点的结点，其转移值事实上等于到最近的往下的关键点的最小边权。
对于每次查询构建虚树即可。
Code
/*
* luogu.2495.cpp
* Copyright (C) 2022 Woshiluo Luo <[email protected]>
*
* 「Two roads diverged in a wood,and I—
* I took the one less traveled by,
* And that has made all the difference.」
*
* Distributed under terms of the GNU AGPLv3+ license.
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
typedef const int cint;
typedef long long ll;
typedef unsigned long long ull;
inline bool isdigit( const char cur ) { return cur >= '0' && cur <= '9'; }/*{{{*/
template <class T>
T Max( T a, T b ) { return a > b? a: b; }
template <class T>
T Min( T a, T b ) { return a < b? a: b; }
template <class T>
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T>
void chk_Min( T &a, T b ) { if( b < a ) a = b; }
template <typename T>
T read() {
T sum = 0, fl = 1;
char ch = getchar();
for (; isdigit(ch) == 0; ch = getchar())
if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
return sum * fl;
}
template <class T>
T pow( T a, int p ) {
T res = 1;
while( p ) {
if( p & 1 )
res = res * a;
a = a * a;
p >>= 1;
}
return res;
}/*}}}*/
const int N = 3e5 + 1e4;
const int K = 22;
const int INF = 0x3f3f3f3f;
struct Edge {/*{{{*/
int to, next, val;
} e[ N << 1 ];
int ehead[N], ecnt;
void add_edge( cint cur, cint to, cint val ) {
ecnt ++;
e[ecnt].to = to;
e[ecnt].next = ehead[cur];
e[ecnt].val = val;
ehead[cur] = ecnt;
}/*}}}*/
int idx;
int dfn[N], dep[N];
int fa[N][K], min[N][K];
void dfs( cint cur, cint la ) {/*{{{*/
idx ++; dfn[cur] = idx;
fa[cur][0] = la; dep[cur] = dep[la] + 1;
for( int k = 1; k < K; k ++ ) {
if( fa[cur][ k - 1 ] ) {
fa[cur][k] = fa[ fa[cur][ k - 1 ] ][ k - 1 ];
min[cur][k] = Min( min[ fa[cur][ k - 1 ] ][ k - 1 ], min[cur][ k - 1 ] );
}
}
for( int i = ehead[cur]; i; i = e[i].next ) {
if( e[i].to == la )
continue;
cint to = e[i].to;
min[to][0] = e[i].val;
dfs( to, cur );
}
}/*}}}*/
int get_lca( int from, int to ) {/*{{{*/
if( dep[from] < dep[to] )
std::swap( from, to );
for( int k = K - 1; k >= 0; k -- ) {
if( fa[from][k] && dep[ fa[from][k] ] >= dep[to] )
from = fa[from][k];
}
if( from == to )
return from;
for( int k = K - 1; k >= 0; k -- ) {
if( fa[from][k] && fa[to][k] && fa[from][k] != fa[to][k] ) {
from = fa[from][k];
to = fa[to][k];
}
}
return fa[from][0];
}/*}}}*/
// should promse: lca(from,to) = from
int get_min( cint from, cint to ) {/*{{{*/
int cur = to;
int res = INF;
for( int k = K - 1; k >= 0; k -- ) {
if( fa[cur][k] && dep[ fa[cur][k] ] >= dep[from] ) {
chk_Min( res, min[cur][k] );
cur = fa[cur][k];
}
}
return res;
}/*}}}*/
ll f[N];
bool impo[N];
void dp( cint cur ) {/*{{{*/
f[cur] = 0;
for( int i = ehead[cur]; i; i = e[i].next ) {
cint to = e[i].to;
dp(to);
if( impo[to] )
f[cur] += e[i].val;
else
f[cur] += Min( f[to], (ll)e[i].val );
}
}/*}}}*/
int main() {
#ifdef woshiluo
freopen( "luogu.2495.in", "r", stdin );
freopen( "luogu.2495.out", "w", stdout );
#endif
cint n = read<int>();
for( int i = 1; i < n; i ++ ) {
cint u = read<int>();
cint v = read<int>();
cint w = read<int>();
add_edge( u, v, w );
add_edge( v, u, w );
}
dfs( 1, 0 );
ecnt = 0;
for( int i = 1; i <= n; i ++ )
ehead[i] = 0;
cint m = read<int>();
for( int _ = 1; _ <= m; _ ++ ) {
std::vector<int> list, set;
int k = read<int>();
for( int i = 1; i <= k; i ++ ) {
list.push_back( read<int>() );
impo[ list.back() ] = true;
}
std::sort( list.begin(), list.end(), []( const int &_a, const int &_b ) { return dfn[_a] < dfn[_b]; } );
std::vector<int> st;
st.push_back(1); set.push_back(1);
auto try_pop = [&]() {
cint cur = st.back(); st.pop_back();
set.push_back(cur);
add_edge( st.back(), cur, get_min( st.back(), cur ) );
};
for( auto &x: list ) {
while(1) {
cint lca = get_lca( x, st.back() );
if( lca == st.back() || dfn[ st[ st.size() - 2 ] ] < dfn[lca] )
break;
try_pop();
}
cint lca = get_lca( x, st.back() );
if( lca != st.back() ) {
cint tmp = st.back(); st.pop_back();
st.push_back(lca); st.push_back(tmp);
try_pop();
}
st.push_back(x);
}
while( st.size() > 1 )
try_pop();
dp(1);
printf( "%lld\n", f[1] );
ecnt = 0;
for( auto &x: set ) {
ehead[x] = 0;
impo[x] = false;
}
}
}