一般用到只跟点数有关，多次查询的题目时就会用到虚树，同时还要支持快速查询点之间的信息
下面是消耗战的例子
注意，这道题目的例子有点特殊，所以那位神仙的代码并不是一般题目通用的，但是我的代码是通用的
注意，1一定要加入点集中
#include<bits/stdc++.h>
#define vit vector<int>::iterator
typedef long long ll;
using namespace std;
const int N=2.9e5;
const int Log=20;
const ll inf=1e15+7;
struct edge
{
int to,nxt,co;
}e[N*2];
int h[N],E=0;
int siz[N],son[N],dfn[N],mp[N],pa[N],dep[N],top[N],tim=0;
ll st[Log+5][N],p2[Log+5],l2[N],tof[N];
int a[N];
int n,m,k;
int s[N],Top=0;
int used[N];
ll f[N];
vector<int> g[N];
void addedge(int u,int v,int w)
{
E++;
e[E].to=v,e[E].nxt=h[u],e[E].co=w;
h[u]=E;
return;
}
void vaddedg(int u,int v)
{
g[u].push_back(v);
return;
}
void dfs1(int u,int fa,ll co)
{
tof[u]=co;
dep[u]=dep[fa]+1;
siz[u]=1;
pa[u]=fa;
son[u]=-1;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].to;
int w=e[i].co;
if(v==fa) continue;
dfs1(v,u,w);
siz[u]+=siz[v];
if(son[u]==-1||siz[son[u]]<siz[v]) son[u]=v;
}
return;
}
void dfs2(int u,int fa)
{
if(!top[u]) top[u]=u;
tim++;
dfn[u]=tim;
mp[tim]=u;
st[0][tim]=tof[u];
if(son[u]!=-1) top[son[u]]=top[u],dfs2(son[u],u);
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa||v==son[u]) continue;
dfs2(v,u);
}
return;
}
int LCA(int u,int v)
{
for(;top[u]!=top[v];)
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
u=pa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
return u;
}
ll que(int l,int r)
{
if(l>r) return inf;
int s=l2[r-l+1];
return min(st[s][l],st[s][r-p2[s]+1]);
}
ll cal(int u,int to)
{
ll res=inf;
for(;dep[top[u]]>dep[to];u=pa[top[u]]) res=min(res,que(dfn[top[u]],dfn[u]));
res=min(res,que(dfn[to]+1,dfn[u]));
return res;
}
void Init()
{
p2[0]=1;
for(int i=1;i<=Log;i++) p2[i]=p2[i-1]*2;
l2[0]=-1;
for(int i=1;i<=n;i++) l2[i]=l2[i/2]+1;
for(int i=1;i<=Log;i++)
for(int j=1;j+p2[i]-1<=n;j++)
st[i][j]=min(st[i-1][j],st[i-1][j+p2[i-1]]);
return;
}
int cmp(int a,int b)
{
return dfn[a]<dfn[b];
}
void vins(int x)
{
if(!Top) return void(s[++Top]=x);
int lca=LCA(x,s[Top]);
if(lca==s[Top]) return void(s[++Top]=x);
while(Top>1&&dfn[s[Top-1]]>=dfn[lca]) vaddedg(s[Top-1],s[Top]),Top--;
if(lca!=s[Top]) vaddedg(lca,s[Top]),s[Top]=lca;
s[++Top]=x;
return;
}
void DP(int u,ll co)
{
f[u]=0;
for(vit it=g[u].begin();it!=g[u].end();it++)
{
int v=*it;
int w=cal(v,u);
DP(v,w);
f[u]+=f[v];
}
if(used[u]) f[u]=co;
else f[u]=min(f[u],co);
g[u].clear();
return;
}
void build(int k)
{
for(int i=1;i<=k;i++) scanf("%d",&a[i]);
sort(a+1,a+k+1,cmp);
s[Top=1]=1;
for(int i=1;i<=k;i++)
{
vins(a[i]);
used[a[i]]=1;
}
while(Top>1) vaddedg(s[Top-1],s[Top]),Top--;
DP(1,inf);
for(int i=1;i<=k;i++) used[a[i]]=0;
return;
}
int main()
{
scanf("%d",&n);
int u,v,w;
for(int i=1;i<=n-1;i++)
{
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
dep[0]=-1;
dfs1(1,0,inf);
dfs2(1,0);
Init();
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&k);
build(k);
printf("%lld\n",f[1]);
}
return 0;
}