fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define db long double
  4. #define pll pair<ll,ll>
  5. #define foru(i,a,b) for(int i=(a);i<=(ll)(b);i++)
  6. #define ford(i,a,b) for(int i=(a);i>=(ll)(b);i--)
  7. #define ALL(a) (a).begin(),(a).end()
  8. #define ROUND(i) fixed<<setprecision(i)
  9. #define fi first
  10. #define se second
  11. using namespace std;
  12. const ll MAXN=3e5+55;
  13. const ll LOG=18;
  14. const ll INF=1e18;
  15. ll n,Q;
  16. vector<pll>adj[MAXN];
  17. ll dep[MAXN],st[MAXN],fn[MAXN],tdfs=0;
  18. ll up[MAXN][LOG+5],mnw[MAXN][LOG+5];
  19. void dfsprep(ll u,ll p){
  20.     st[u]=++tdfs;
  21.     for(auto [v,w]:adj[u])if(v!=p){
  22.         dep[v]=dep[u]+1;
  23.         up[v][0]=u;
  24.         mnw[v][0]=w;
  25.         foru(i,1,LOG){
  26.             up[v][i]=up[up[v][i-1]][i-1];
  27.             mnw[v][i]=min(mnw[v][i-1],mnw[up[v][i-1]][i-1]);
  28.         }
  29.         dfsprep(v,u);
  30.     }
  31.     fn[u]=tdfs;
  32. }
  33. pll lift(ll u,ll k){
  34.     ll w=1e18;
  35.     ford(i,LOG,0)if(k>>i&1)w=min(w,mnw[u][i]),u=up[u][i];
  36.     return {u,w};
  37. }
  38. ll LCA(ll u,ll v){
  39.     if(dep[u]>dep[v])swap(u,v);
  40.     v=lift(v,dep[v]-dep[u]).fi;
  41.     if(u==v)return u;
  42.     ford(i,LOG,0)if(up[u][i]!=up[v][i])u=up[u][i],v=up[v][i];
  43.     return up[u][0];
  44. }
  45. bool inside(ll p,ll u){
  46.     return st[p]<=st[u]&&fn[u]<=fn[p];
  47. }
  48. vector<ll>ke[MAXN],ver;
  49. ll dp[MAXN],k;
  50. void makeTree(){
  51.     sort(ALL(ver),[&](ll &u,ll &v){return st[u]<st[v];});
  52.     ll hehe=ver.size()-1;
  53.     foru(i,1,hehe){
  54.         ver.push_back(LCA(ver[i-1],ver[i]));
  55.     }
  56.     sort(ALL(ver),[&](ll &u,ll &v){return st[u]<st[v];});
  57.     ver.erase(unique(ALL(ver)),ver.end());
  58.     stack<ll>st;st.push(ver[0]);
  59.     hehe=ver.size()-1;
  60.     foru(i,1,hehe){
  61.         while(st.size()&&!inside(st.top(),ver[i]))st.pop();
  62.         ke[st.top()].push_back(ver[i]);
  63.         st.push(ver[i]);
  64.     }
  65. }
  66. void DFS(ll u,ll p){
  67.     ll sum=0;
  68.     for(auto v:ke[u]){
  69.         DFS(v,u);
  70.         sum+=dp[v];
  71.     }
  72.     if(dp[u]<1e17){
  73.         dp[u]=min(dp[u],lift(u,dep[u]-dep[p]).se);
  74.     }
  75.     else{
  76.         dp[u]=min(sum,lift(u,dep[u]-dep[p]).se);
  77.     }
  78. }
  79. void solveQuery(){
  80.     cin>>k;ver={};
  81.     foru(i,1,k){
  82.         ll u;cin>>u;
  83.         ver.push_back(u);
  84.         dp[u]=mnw[u][0];
  85.     }
  86.     makeTree();
  87.     DFS(ver[0],1);
  88.     cout<<dp[ver[0]]<<'\n';
  89.     for(auto u:ver)ke[u]={},dp[u]=1e18;
  90. }
  91. signed main(){
  92.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  93.  
  94.     cin>>n;
  95.     foru(i,1,n-1){
  96.         ll u,v,w;cin>>u>>v>>w;
  97.         adj[u].push_back({v,w});
  98.         adj[v].push_back({u,w});
  99.     }
  100.  
  101.     memset(mnw,0x3f,sizeof(mnw));
  102.     memset(dp,0x3f,sizeof(dp));
  103.     dfsprep(1,0);
  104.  
  105.     cin>>Q;
  106.     while(Q--){
  107.         solveQuery();
  108.     }
  109.     return 0;
  110. }
Success #stdin #stdout 0.02s 77684KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CSJg8J
language:
C++14 (gcc 8.3)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!