第一次学习虚树,就是把无关的点去掉。S里维护一条链即可。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;
const LL Maxm=;
const LL Maxn=;
const LL Inf=1e60;
struct Node {LL to,next,w;}edge[Maxm],edge2[Maxm];
LL head[Maxn],head2[Maxn],dep[Maxn],H[Maxn],mark[Maxn],size[Maxn];
LL top[Maxn],father[Maxn],f[Maxn],S[Maxn],mn[Maxn];
LL cnt1,cnt2,tot,n,u,v,w,tp,m,K;
bool vis[Maxn];
inline void Add(LL u,LL v,LL w)
{edge[cnt1].to=v;edge[cnt1].next=head[u];edge[cnt1].w=w;head[u]=cnt1++;
edge[cnt1].to=u;edge[cnt1].next=head[v];edge[cnt1].w=w;head[v]=cnt1++;}
inline void Add2(LL u,LL v)
{if (u==v) return; edge2[cnt2].to=v;edge2[cnt2].next=head2[u];head2[u]=cnt2++;}
inline LL Min(LL x,LL y) {return x>y?y:x;}
inline void Get_Int(LL &x)
{
x=; char ch=getchar(); LL f=;
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();} x*=f;
}
inline void Put_Int(LL x)
{
char ch[]; LL top=;
if (x==) ch[++top]='';
while (x) ch[++top]=x%+'',x/=;
while (top) putchar(ch[top--]); putchar('\n');
}
//================================================
void Dfs1(LL u)
{
mark[u]=++tot;vis[u]=true; size[u]=;
for (LL i=head[u];i!=-;i=edge[i].next)
if (!vis[edge[i].to])
{
dep[edge[i].to]=dep[u]+;
father[edge[i].to]=u;
mn[edge[i].to]=Min(mn[u],edge[i].w);
Dfs1(edge[i].to);
size[u]+=size[edge[i].to];
}
}
void Dfs2(LL u,LL chain)
{
top[u]=chain; vis[u]=true; LL k=;
for (int i=head[u];i!=-;i=edge[i].next)
if (!vis[edge[i].to] && (size[edge[i].to]>size[k] || k==)) k=edge[i].to;
if (k==) return;
Dfs2(k,chain);
for (int i=head[u];i!=-;i=edge[i].next)
if (!vis[edge[i].to] && i!=k) Dfs2(edge[i].to,edge[i].to);
}
inline LL Lca(LL u,LL v)
{
while (true)
{
if (top[u]==top[v]) return dep[u]>dep[v]?v:u;
if (dep[top[u]]>dep[top[v]]) u=father[top[u]];
else v=father[top[v]];
}
}
//=============================================================
inline bool cmp(LL x,LL y) {return mark[x]<mark[y];}
void Dp(LL u)
{ vis[u]=true; f[u]=mn[u]; LL ret=;
for (int i=head2[u];i!=-;i=edge2[i].next)
{
Dp(edge2[i].to);
ret+=f[edge2[i].to];
}
head2[u]=-;
if (ret) f[u]=Min(f[u],ret);
}
void Solve()
{
Get_Int(K);
for (int i=;i<=K;i++) Get_Int(H[i]);
sort(H+,H+K+,cmp);
tp=tot=; H[++tot]=H[];
for (int i=;i<=K;i++)
if (Lca(H[tot],H[i])!=H[tot]) H[++tot]=H[i];
cnt2=;
S[++tp]=;
for (int i=;i<=tot;i++)
{
LL u=H[i],f=Lca(u,S[tp]);
while (true)
{
if (dep[f]>=dep[S[tp-]])
{
Add2(f,S[tp--]);
if (S[tp]!=f) S[++tp]=f;
break;
}
Add2(S[tp-],S[tp]); tp--;
}
if (S[tp]!=u) S[++tp]=u;
}
while (--tp) Add2(S[tp],S[tp+]);
Dp();
Put_Int(f[]);
}
int main()
{
Get_Int(n);
memset(head,-,sizeof(head));cnt1=;
for (int i=;i<n;i++)
{
Get_Int(u),Get_Int(v),Get_Int(w);
Add(u,v,w),Add(v,u,w);
} father[]=; dep[]=; tot=; mn[]=Inf;
memset(vis,false,sizeof(vis));Dfs1();
memset(vis,false,sizeof(vis));Dfs2(,);
memset(head2,-,sizeof(head2));
Get_Int(m);
for (int i=;i<=m;i++) Solve();
return ;
}
C++