Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define gc c=getchar()
- #define r(x) read(x)
- #define ll long long
- template<typename T>
- inline void read(T&x){
- x=0;T k=1;char gc;
- while(!isdigit(c)){if(c=='-')k=-1;gc;}
- while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
- }
- const int N=250005;
- int ecnt;
- int fir[N],nex[N<<1],to[N<<1],w[N<<1];
- inline void addedge(int u,int v,int c){
- nex[++ecnt]=fir[u],fir[u]=ecnt,to[ecnt]=v,w[ecnt]=c;
- nex[++ecnt]=fir[v],fir[v]=ecnt,to[ecnt]=u,w[ecnt]=c;
- }
- int fa[N];
- ll val[N];
- int dep[N];
- int siz[N];
- int son[N];
- void dfs1(int x,int f){
- fa[x]=f;
- siz[x]=1;
- dep[x]=dep[f]+1;
- for(int i=fir[x];i;i=nex[i]){
- int v=to[i];
- if(v==f)continue;
- val[v]=min(val[x],(ll)w[i]);
- dfs1(v,x);
- siz[x]+=siz[v];
- if(siz[son[x]]<siz[v])son[x]=v;
- }
- }
- int top[N];
- int dfn[N];
- int dfs_clock;
- void dfs2(int x,int t){
- top[x]=t;
- dfn[x]=++dfs_clock;
- if(!son[x])return ;
- dfs2(son[x],t);
- for(int i=fir[x];i;i=nex[i]){
- int v=to[i];
- if(v==fa[x]||v==son[x])continue;
- dfs2(v,v);
- }
- }
- inline int lca(int u,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;
- }
- inline bool cmp(const int &a,const int &b){
- return dfn[a]<dfn[b];
- }
- int Top;
- int sta[N];
- vector<int>G[N];
- inline void ins(int x){
- if(Top==1){
- sta[++Top]=x;
- return ;
- }
- int t=lca(x,sta[Top]);
- if(t==sta[Top])return ;
- while(Top>1&&dfn[sta[Top-1]]>=dfn[t]){
- G[sta[Top-1]].push_back(sta[Top]);
- --Top;
- }
- if(sta[Top]!=t){
- G[t].push_back(sta[Top]);
- sta[Top]=t;
- }
- sta[++Top]=x;
- }
- inline ll dfs3(int x){
- if(!G[x].size())return val[x];
- ll sum=0;
- for(int i=0;i<G[x].size();++i){
- sum+=dfs3(G[x][i]);
- }
- G[x].clear();
- return min(sum,val[x]);
- }
- int a[N];
- int main(){
- // freopen(".in","r",stdin);
- // freopen(".out","w",stdout);
- int n;r(n);
- for(int i=1;i<n;++i){
- int u,v,w;
- r(u),r(v),r(w);
- addedge(u,v,w);
- }
- val[1]=1e18;
- dfs1(1,0);
- dfs2(1,0);
- int m;r(m);
- while(m--){
- int tot;r(tot);
- for(int i=1;i<=tot;++i){
- r(a[i]);
- }
- sort(a+1,a+tot+1,cmp);
- sta[Top=1]=1;
- for(int i=1;i<=tot;++i){
- ins(a[i]);
- }
- while(Top>1){
- G[sta[Top-1]].push_back(sta[Top]);
- --Top;
- }
- printf("%lld\n",dfs3(1));
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment