虚树

适用题目特征

树上有若干关键点（每次询问给出若干关键点），且关键点的总数是与树大小同阶，也就是说实际上一次询问中关键点对于整棵树来说是很稀疏的，所以需要让复杂度由关键点的总数来决定。即把一整颗大树浓缩成一颗小树。

原理

仅包含关键点和他们的LCA的树不会丢失信息。

例题

Luogu P2495
代码如下

/*
Luogu P2495
*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=250000+5;
const int maxlogn=23;
const int maxm=500000+5;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int n,m;
int t;
int head[maxn],tot=1;
int head2[maxn],tot2;
struct node{
    int from,to;ll w;
}edge[maxm<<1],edge2[maxm<<1];
void add(int from,int to,ll w){
    edge[++tot].from=head[from];
    edge[tot].to=to,edge[tot].w=w,head[from]=tot;
}
void add2(int from,int to){
    edge2[++tot2].from=head2[from];
    edge2[tot2].to=to,head2[from]=tot2;
}
ll mn[maxn];
int d[maxn],f[maxn][maxlogn];
int dfn[maxn],cnt=0;
void dfs(int x){
    dfn[x]=++cnt;
    rep(j,1,t) f[x][j]=f[f[x][j-1]][j-1];
    for(int i=head[x];i;i=edge[i].from){
        int y=edge[i].to;ll w=edge[i].w;
        if(dfn[y]) continue;
        d[y]=d[x]+1,mn[y]=min(mn[x],w),f[y][0]=x;
        dfs(y);
    }
} 
int lca(int x,int y){
    if(d[x]>d[y]) swap(x,y);
    rrep(i,t,0) if(d[f[y][i]]>=d[x]) y=f[y][i];
    if(x==y) return x;
    rrep(i,t,0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
int tr[maxn],q[maxn];
ll dp(int x){ //edge in virtural tree is direct, so don't need to consider edge like <son,fa>
    ll sum=0ll,res;
    for(int i=head2[x];i;i=edge2[i].from){
        int y=edge2[i].to;
        sum+=dp(y);
    }
    if(q[x]) res=mn[x];
    else res=min(mn[x],sum); //cut one edge on [1,x] or cut all child of i from i
    q[x]=0,head2[x]=0;
    return res;
}
bool cmp(int x,int y){
    return dfn[x]<dfn[y];
}
int st[maxn],top;
void build(int num){
    tot2=1;
    sort(tr+1,tr+num+1,cmp);
    st[top=1]=tr[1];
//  rep(i,1,num) D(tr[i]);E;
    rep(i,2,num){
        int now=tr[i],p=lca(now,st[top]);
        while(1){
            if(d[p]>=d[st[top-1]]){
                if(p!=st[top]){
                    add2(p,st[top]);
                    if(p!=st[top-1]) st[top]=p;
                    else top--;
                }
                break;
            }
            else add2(st[top-1],st[top]),top--;
        }
        st[++top]=now;
    }
    while(--top) add2(st[top],st[top+1]);
}
void solve(){
    t=(int)(log(n)/log(2))+1; 
    mn[1]=INF;d[1]=1;
    dfs(1);
//  rep(i,1,n) D(d[i]);E;
    scanf("%d",&m);
    int num;
    while(m--){ 
        scanf("%d",&num);
        rep(i,1,num) scanf("%d",&tr[i]),q[tr[i]]=1;
        build(num);
        ll res=dp(st[1]);
        printf("%lld\n",res);
    }
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("消耗战.in","r",stdin);
    scanf("%d",&n);
    int from,to;ll w;
    rep(i,1,n-1) scanf("%d%d%lld",&from,&to,&w),add(from,to,w),add(to,from,w);
    solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif