[文章目录]
Description
在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。
侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到1号岛屿上）。不过侦查部门还发现了这台机器只能够使用m次，所以我们只需要把每次任务完成即可。2<=n<=250000，sigma(ki)<=500000
虚树
构建虚树的时候倍增求两点路径上最小边权，然后就是很简单的树形DP了。
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define N 251000
const int inf=0x3f3f3f3f;
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int re=0; char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
return re;
}
int n,head[N],to[N<<1],nxt[N<<1],f[N<<1],cnt;
inline void add(int z,int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=z;
}
int m,k,d[N],z[N],in[N],dep[N],fa[N][20],Log[N],mi[N][20],tot;
void dfs(int x,int pre)
{
in[x]=++tot;
for(int i=1;i<=Log[dep[x]];++i)
fa[x][i]=fa[fa[x][i-1]][i-1],mi[x][i]=min(mi[x][i-1],mi[fa[x][i-1]][i-1]);
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
dep[to[i]]=dep[x]+1,fa[to[i]][0]=x,mi[to[i]][0]=f[i],dfs(to[i],x);
}
bool cmp(int x,int y){return in[x]<in[y];}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
int i,t=dep[x]-dep[y];
for(i=0;i<=Log[t];++i) if((t>>i)&1) x=fa[x][i];
if(x==y) return x;
for(i=Log[dep[x]];i>=0;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int Head[N],To[N<<1],Nxt[N<<1],F[N<<1],Cnt;
ll dp[N];
bool vis[N];
inline int getmi(int x,int y)
{
if(dep[x]>dep[y]) swap(x,y);
int t=dep[y]-dep[x],re=inf;
for(int i=0;i<=Log[t];++i) if((t>>i)&1) re=min(re,mi[y][i]),y=fa[y][i];
return re;
}
inline void Add(int x,int y)
{
int c=getmi(x,y);
To[++Cnt]=y; Nxt[Cnt]=Head[x]; Head[x]=Cnt; F[Cnt]=c;
To[++Cnt]=x; Nxt[Cnt]=Head[y]; Head[y]=Cnt; F[Cnt]=c;
}
void Dfs(int x,int pre)
{
dp[x]=0;
for(int i=Head[x];i;i=Nxt[i]) if(To[i]!=pre)
{
Dfs(To[i],x);
dp[x]+=min((ll)F[i],dp[To[i]]);
}
Head[x]=0;
if(vis[x]) dp[x]=1ll<<60;
}
int main()
{
n=read(); int i;
for(i=1;i<n;++i) add(read(),read(),read());
for(i=2;i<=n;++i) Log[i]=Log[i>>1]+1;
dfs(1,0); m=read(); int anc,top;
while(m--)
{
for(i=1;i<=k;++i) vis[d[i]]=0;
top=Cnt=0; k=read();
for(i=1;i<=k;++i) d[i]=read(),vis[d[i]]=1;
sort(d+1,d+k+1,cmp); z[++top]=1;
for(i=1;i<=k;++i)
{
anc=lca(z[top],d[i]);
while(top>1&&dep[z[top-1]]>dep[anc]) Add(z[top-1],z[top]),top--;
if(z[top]!=anc) Add(anc,z[top]); top--;
if(z[top]!=anc) z[++top]=anc; z[++top]=d[i];
}
while(top>1) Add(z[top-1],z[top]),top--;
Dfs(1,0); printf("%lld\n",dp[1]);
}
return 0;
}