fork download 
  1. #include "race.h"
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. #define MAXN 200005
  7. #define MAXK 1000006
  8. typedef pair<int,int> pii;
  9.  
  10. static int N,K,M,MM,ans=1e9;
  11. static bool del[MAXN];
  12. static vector<int> con[MAXN],conv[MAXN];
  13.  
  14. static int mom[MAXN],cnt[MAXN],dep[MAXN],chk[MAXN];
  15. static int min_cnt[MAXK],min_cnt_chk[MAXK],head,tail;
  16. static pii que[MAXN];
  17.  
  18. void ff(int n)
  19. {
  20.     int i,k;
  21.     cnt[n] = 1; chk[n] = M;
  22.     for (i=con[n].size();i--;){
  23.         k = con[n][i];
  24.         if (del[k] || chk[k] == M) continue;
  25.         mom[k] = n;
  26.         ff(k);
  27.         cnt[n] += cnt[k];
  28.     }
  29. }
  30.  
  31. int get_cen(int n,int all)
  32. {
  33.     int i,k;
  34.     for (i=con[n].size();i--;){
  35.         k = con[n][i];
  36.         if (del[k] || k == mom[n]) continue;
  37.         if (cnt[k] > all/2) return get_cen(k,all);
  38.     }
  39.     return n;
  40. }
  41.  
  42. void dfs(int n,int sum)
  43. {
  44.     int i,k,v;
  45.     chk[n] = M;
  46.     que[tail++] = pii(sum,dep[n]);
  47.     for (i=con[n].size();i--;){
  48.         k = con[n][i]; v = conv[n][i];
  49.         if (del[k] || chk[k] == M) continue;
  50.         mom[k] = n; dep[k] = dep[n]+1;
  51.         dfs(k,sum+v);
  52.     }
  53. }
  54.  
  55. void dnc(int root)
  56. {
  57.     int i,j,k,v,cen;
  58.     pii q;
  59.     ++M; ff(root);
  60.     cen = get_cen(root,cnt[root]);
  61.     /* process */
  62.     min_cnt[0] = 0; min_cnt_chk[0] = ++MM;
  63.     for (i=con[cen].size();i--;){
  64.         k = con[cen][i]; v = conv[cen][i];
  65.         if (del[k]) continue;
  66.         head = tail = 0; dep[k] = 1;
  67.         ++M; chk[cen] = M; dfs(k,v);
  68.         for (j=0;j<tail;j++){
  69.             q = que[j];
  70.             if (q.first > K) continue;
  71.             if (min_cnt_chk[K-q.first] == MM) ans = min(ans,min_cnt[K-q.first]+q.second);
  72.         }
  73.         while (head != tail){
  74.             q = que[head++];
  75.             if (q.first > K) continue;
  76.             if (min_cnt_chk[q.first] != MM || min_cnt[q.first] > q.second){
  77.                 min_cnt_chk[q.first] = MM;
  78.                 min_cnt[q.first] = q.second;
  79.             }
  80.         }
  81.     }
  82.     /* process end */
  83.     del[cen] = 1;
  84.     for (i=con[cen].size();i--;){
  85.         k = con[cen][i];
  86.         if (del[k]) continue;
  87.         dnc(k);
  88.     }
  89. }
  90.  
  91. int best_path(int n, int k, int H[][2], int L[])
  92. {
  93.     int i,j,a,b,c;
  94.     N = n; K = k;
  95.     for (i=0;i<N-1;i++){
  96.         a = H[i][0]+1, b = H[i][1]+1, c = L[i];
  97.         con[a].push_back(b); conv[a].push_back(c);
  98.         con[b].push_back(a); conv[b].push_back(c);
  99.     }
  100.     dnc(1);
  101.     return ans==1e9?-1:ans;
  102. }
  103.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Sqnj8l
language:
C++ (gcc 8.3)
created:
11 years 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!