适用题目特征
树上有若干关键点（每次询问给出若干关键点），且关键点的总数是与树大小同阶，也就是说实际上一次询问中关键点对于整棵树来说是很稀疏的，所以需要让复杂度由关键点的总数来决定。即把一整颗大树浓缩成一颗小树。
原理
仅包含关键点和他们的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
