建出虚树dp。
把询问点按dfs序排序,用一个以dfs序为关键字的单调栈(以深度为关键字也是一样的),每次将一个询问点与栈顶的点的lca入栈,再将这个询问点入栈,在这个过程中建出一棵树就是虚树。具体看代码。
#include<bits/stdc++.h> #define N 250005 using namespace std; typedef long long LL; int n,m,q; struct edge{ edge* s; int v,w; }e[N<<1],*back=e,*h[N]; void add( int u,int v,int w){ h[u]=&(*back++ =(edge){h[u],v,w}); h[v]=&(*back++ =(edge){h[v],u,w}); } void add(int u,int v){ h[u]=&(*back++ =(edge){h[u],v}); } typedef int ds[N]; ds d,num,p,size,son,top,t,z,v,a; void dfs1(int u){ d[u]=d[p[u]]+1; size[u]=1; int s=0; for(edge* i=h[u];i;i=i->s) if(i->v!=p[u]){ p[i->v]=u; t[i->v]=min(t[u],i->w); dfs1(i->v); size[u]+=size[i->v]; if(s<size[i->v]) s=size[son[u]=i->v]; } } void dfs2(int u){ static int cnt; num[u]=++cnt; if(size[u]!=1){ top[son[u]]=top[u]; dfs2(son[u]); } for(edge*& i=h[u];i;i=i->s) if(i->v!=p[u] &&i->v!=son[u]) dfs2(top[i->v]=i->v); } int lca(int s,int t){ while(top[s]!=top[t]){ if(d[top[s]]<d[top[t]]) swap(s,t); s=p[top[s]]; } return d[s]<d[t]?s:t; } bool foo(int i,int j){ return num[i]<num[j]; } LL dp(int u){ LL s=0; for(edge*& i=h[u];i;i=i->s) s+=dp(i->v); return u==1||s<t[u] &&z[u]!=q+1?s:t[u]; } void writeln(int u){ printf("%d\n",u); } void writeln(LL u){ printf("%lld\n",u); } int main(){ scanf("%d",&n); for(int i=1;i!=n;++i){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); } t[1]=1e9; dfs1(1); dfs2(top[1]=1); scanf("%d",&q); while(q--){ scanf("%d",&m); for(int j=0;j!=m;++j) scanf("%d",a+j); sort(a,a+m,foo); back=e; int i=v[1]=1,j=0; while(j!=m){ int u=lca(v[i],a[j]); while(d[u]<d[v[i]]){ --i; if(d[u]<d[v[i]]) add(v[i],v[i+1]); else{ add(u,v[i+1]); v[i+=v[i]!=u]=u; } } z[a[j]]=q+1; v[++i]=a[j++]; } while(--i) add(v[i],v[i+1]); writeln(dp(1)); } }