yicongli

LG2495

Mar 3rd, 2019
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.30 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const int N=250005;
  17.  
  18. int ecnt;
  19. int fir[N],nex[N<<1],to[N<<1],w[N<<1];
  20.  
  21. inline void addedge(int u,int v,int c){
  22.     nex[++ecnt]=fir[u],fir[u]=ecnt,to[ecnt]=v,w[ecnt]=c;
  23.     nex[++ecnt]=fir[v],fir[v]=ecnt,to[ecnt]=u,w[ecnt]=c;
  24. }
  25.  
  26. int fa[N];
  27. ll val[N];
  28. int dep[N];
  29. int siz[N];
  30. int son[N];
  31.  
  32. void dfs1(int x,int f){
  33.     fa[x]=f;
  34.     siz[x]=1;
  35.     dep[x]=dep[f]+1;
  36.     for(int i=fir[x];i;i=nex[i]){
  37.         int v=to[i];
  38.         if(v==f)continue;
  39.         val[v]=min(val[x],(ll)w[i]);
  40.         dfs1(v,x);
  41.         siz[x]+=siz[v];
  42.         if(siz[son[x]]<siz[v])son[x]=v;
  43.     }
  44. }
  45.  
  46. int top[N];
  47. int dfn[N];
  48. int dfs_clock;
  49.  
  50. void dfs2(int x,int t){
  51.     top[x]=t;
  52.     dfn[x]=++dfs_clock;
  53.     if(!son[x])return ;
  54.     dfs2(son[x],t);
  55.     for(int i=fir[x];i;i=nex[i]){
  56.         int v=to[i];
  57.         if(v==fa[x]||v==son[x])continue;
  58.         dfs2(v,v);
  59.     }
  60. }
  61.  
  62. inline int lca(int u,int v){
  63.     while(top[u]!=top[v]){
  64.         if(dep[top[u]]<dep[top[v]])swap(u,v);
  65.         u=fa[top[u]];
  66.     }
  67.     return dep[u]<dep[v]?u:v;
  68. }
  69.  
  70. inline bool cmp(const int &a,const int &b){
  71.     return dfn[a]<dfn[b];
  72. }
  73.  
  74. int Top;
  75. int sta[N];
  76.  
  77. vector<int>G[N];
  78.  
  79. inline void ins(int x){
  80.     if(Top==1){
  81.         sta[++Top]=x;
  82.         return ;
  83.     }
  84.     int t=lca(x,sta[Top]);
  85.     if(t==sta[Top])return ;
  86.     while(Top>1&&dfn[sta[Top-1]]>=dfn[t]){
  87.         G[sta[Top-1]].push_back(sta[Top]);
  88.         --Top;
  89.     }
  90.     if(sta[Top]!=t){
  91.         G[t].push_back(sta[Top]);
  92.         sta[Top]=t;
  93.     }
  94.     sta[++Top]=x;
  95. }
  96.  
  97. inline ll dfs3(int x){
  98.     if(!G[x].size())return val[x];
  99.     ll sum=0;
  100.     for(int i=0;i<G[x].size();++i){
  101.         sum+=dfs3(G[x][i]);
  102.     }
  103.     G[x].clear();
  104.     return min(sum,val[x]);
  105. }
  106.  
  107. int a[N];
  108.  
  109. int main(){
  110. //  freopen(".in","r",stdin);
  111. //  freopen(".out","w",stdout);
  112.     int n;r(n);
  113.     for(int i=1;i<n;++i){
  114.         int u,v,w;
  115.         r(u),r(v),r(w);
  116.         addedge(u,v,w);
  117.     }
  118.     val[1]=1e18;
  119.     dfs1(1,0);
  120.     dfs2(1,0);
  121.     int m;r(m);
  122.     while(m--){
  123.         int tot;r(tot);
  124.         for(int i=1;i<=tot;++i){
  125.             r(a[i]);
  126.         }
  127.         sort(a+1,a+tot+1,cmp);
  128.         sta[Top=1]=1;
  129.         for(int i=1;i<=tot;++i){
  130.             ins(a[i]);
  131.         }
  132.         while(Top>1){
  133.             G[sta[Top-1]].push_back(sta[Top]);
  134.             --Top;
  135.         }
  136.         printf("%lld\n",dfs3(1));
  137.     }
  138.     return 0;
  139. }
Advertisement
Add Comment
Please, Sign In to add comment