Description

Input

第一行一個整數n，代表島嶼數量。

接下來n-1行，每行三個整數u,v,w，代表u號島嶼和v號島嶼由一條代價為c的橋梁直接相連，保證1<=u,v<=n且1<=c<=100000。

第n+1行，一個整數m，代表敵方機器能使用的次數。

接下來m行，每行一個整數k_i，代表第i次后，有k_i個島嶼資源豐富，接下來k個整數h₁,h₂,…h_k，表示資源豐富島嶼的編號。

Output

輸出有m行，分別代表每次任務的最小代價。

Sample Input

Sample Output

HINT

 對于100%的數據，2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1

正解：虛樹+樹形dp。

閑得無聊學了下虛樹。虛樹就是說對于每個詢問有k個點，滿足sigma(k)為線性的問題，可以將每次詢問的點提出來新建一棵樹。對于k個結點，可以證明兩兩之間本質不同的lca最多只有k-1個。所以再把他們的lca全部加進去，再加一個公共的lca就行了（這道題是加1）。然后把這些結點按照dfs序從小到大排序，找出兩個相鄰點的lca。再將它們按照dfs序排序，開一個棧，如果棧頂元素是當前待加入結點的祖先，就連一條邊，否則彈出棧頂，然后把當前結點加入棧中。這樣，我們就能成功地建立一棵虛樹了。這題dp還是挺容易的，然而因為鄰接表清零出問題了然后調了半天。。

//It is made by wfj_2048~#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <vector>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#define inf (1e17)#define N (1000010)#define il inline#define RG  #define ll long long#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)using namespace std;struct edge{ int nt,to,dis; }g[N];int head[N],size[N],dfn[N],ed[N],dep[N],top[N],fa[N],son[N],a[N],st[N],vi[N],n,q,num,cnt;ll dis[N];il int gi(){    RG int x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();    if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;}il void insert(RG int from,RG int to,RG int dis){ g[++num]=(edge){head[from],to,dis},head[from]=num; return; }il int cmp(const int &a,const int &b){ return dfn[a]<dfn[b]; }il void dfs1(RG int x,RG int p){    dfn[x]=++cnt,dep[x]=dep[p]+1,fa[x]=p,size[x]=1; RG int v;    for (RG int i=head[x];i;i=g[i].nt){	v=g[i].to; if (v==p) continue;	dis[v]=min(dis[x],(ll)g[i].dis);	dfs1(v,x); size[x]+=size[v];	if (size[son[x]]<=size[v]) son[x]=v;    }    ed[x]=cnt; return;}il void dfs2(RG int x,RG int p,RG int a){    top[x]=a; if (son[x]) dfs2(son[x],x,a);    for (RG int i=head[x];i;i=g[i].nt){	RG int v=g[i].to;	if (v==p || v==son[x]) continue;	dfs2(v,x,v);    }    head[x]=0; return;}il int lca(RG int u,RG int v){    while (top[u]!=top[v]){	if (dep[top[u]]<dep[top[v]]) swap(u,v);	u=fa[top[u]];    }    return dep[u]<dep[v] ? u : v;}il ll dp(RG int x){    if (vi[x]) return dis[x]; RG ll res=0;    for (RG int i=head[x];i;i=g[i].nt) res+=dp(g[i].to);    return min(res,dis[x]);}il void work(){    n=gi(); RG int u,v,w; for (RG int i=1;i<n;++i) u=gi(),v=gi(),w=gi(),insert(u,v,w),insert(v,u,w);    dis[1]=inf,dfs1(1,0),dfs2(1,0,1); q=gi();    while(q--){	RG int k=gi(),M=k; for (RG int i=1;i<=k;++i) vi[a[i]=gi()]=1; sort(a+1,a+k+1,cmp);	for (RG int i=2;i<=k;++i) if (ed[a[i-1]]<dfn[a[i]]) a[++M]=lca(a[i-1],a[i]); a[++M]=1;	sort(a+1,a+M+1,cmp); M=unique(a+1,a+M+1)-a-1; RG int top=1; st[top]=a[1],num=0;	for (RG int i=2;i<=M;++i){	    while (top && ed[st[top]]<dfn[a[i]]) top--;	    insert(st[top],a[i],0),st[++top]=a[i];	}	PRintf("%lld/n",dp(1)); for (RG int i=1;i<=M;++i) vi[a[i]]=head[a[i]]=0;    }    return;}int main(){    File("war");    work();    return 0;}