本身求答案是简单的树上DP,只需要求出根到每个点路径上的最小值,然后考虑割连父亲的边还是割所有儿子即可,但是每次都这样做一次显然不能通过,考虑优化
用虚树来优化:虚树是针对树上一些点建出来的一棵树,上面只有这些点和它们的LCA。显然这样虚树的大小不会超过2*所选点数,这样在缩小了问题规模的同时还保留了原树的性质。
具体的建法:
0.预处理DFS序
1.将所选点按DFS序从小到大排序
2.用栈维护一条从根延伸下来的链,依次将排序后的点nde加入。若栈为空则直接入栈,否则设栈顶为top:
3.求nde和top的lca,讨论:
①lca是top,将nde入栈,跑路
②lca不是top,设栈顶起第二个元素为sec。在lca的DFS序不大于sec时不断将sec与top相连并弹栈
(1)如果lca的DFS序小于top,将lca与top相连,弹栈
(2)如果lca仍然不是top,将lca入栈
(3)将nde入栈
(因为我们按DFS序排序,所以lca不可能是nde)
4.将所有点加入后,不断将sec与top相连并弹栈,直到栈里只有一个元素,这就是虚树的树根
之后就可以愉快地树形DP辣
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int T,n,m,t1,t2,t3,cnt,Cnt,tot,poi;
int P[N],Noww[N],Goal[N],p[N],noww[N],goal[N],val[N],cut[N];
int siz[N],far[N],dep[N],imp[N],top[N],dfn[N],pts[N],stk[N];
long long mini[N];
bool cmp(int a,int b)
{
return dfn[a]<dfn[b];
}
void Link(int f,int t,int v)
{
noww[++cnt]=p[f],p[f]=cnt;
goal[cnt]=t,val[cnt]=v;
noww[++cnt]=p[t],p[t]=cnt;
goal[cnt]=f,val[cnt]=v;
}
void Linka(int f,int t)
{
Noww[++Cnt]=P[f];
Goal[Cnt]=t,P[f]=Cnt;
}
void DFS(int nde,int fth,int dth)
{
int tmp=;
siz[nde]=,far[nde]=fth,dep[nde]=dth;
for(int i=p[nde];i;i=noww[i])
if(goal[i]!=fth)
{
mini[goal[i]]=min(mini[nde],1ll*val[i]);
DFS(goal[i],nde,dth+);
siz[nde]+=siz[goal[i]];
if(siz[goal[i]]>tmp)
tmp=siz[goal[i]],imp[nde]=goal[i];
}
}
void Mark(int nde,int tpp)
{
top[nde]=tpp,dfn[nde]=++tot;
if(imp[nde])
{
Mark(imp[nde],tpp);
for(int i=p[nde];i;i=noww[i])
if(goal[i]!=far[nde]&&goal[i]!=imp[nde])
Mark(goal[i],goal[i]);
}
}
int LCA(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y); x=far[top[x]];
}
return dep[x]<dep[y]?x:y;
}
void Insert(int nde)
{
if(!poi) stk[++poi]=nde;
else
{
int lca=LCA(nde,stk[poi]);
if(lca!=stk[poi])
{
while(poi>&&dfn[lca]<=dfn[stk[poi-]])
Linka(stk[poi-],stk[poi]),poi--;
if(dfn[lca]<dfn[stk[poi]])
Linka(lca,stk[poi]),poi--;
if(lca!=stk[poi])
stk[++poi]=lca;
}
stk[++poi]=nde;
}
}
long long Getans(int nde)
{
long long tmp=;
for(int i=P[nde];i;i=Noww[i])
tmp+=Getans(Goal[i]); P[nde]=;
return cut[nde]?mini[nde]:min(mini[nde],tmp);
}
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)
scanf("%d%d%d",&t1,&t2,&t3),Link(t1,t2,t3);
for(int i=;i<=n;i++) mini[i]=1e12;
DFS(,,),Mark(,);
scanf("%d",&T);
while(T--)
{
scanf("%d",&m),Cnt=poi=;
for(int i=;i<=m;i++) scanf("%d",&pts[i]);
sort(pts+,pts++m,cmp);
for(int i=;i<=m;i++) Insert(pts[i]),cut[pts[i]]=true;
while(poi>) Linka(stk[poi-],stk[poi]),poi--;
printf("%lld\n",Getans(stk[]));
for(int i=;i<=m;i++) cut[pts[i]]=false;
}
return ;
}