fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = int(3e5)+7;
  14. const int maxK = 51;
  15. const ll inf = ll(1e18)+7;
  16.  
  17. int n , k , c[maxN];
  18. vector<ii> g[maxN];
  19. ll dp[maxN][maxK] , DP[maxN] , tmp[maxK];
  20. pair<ii , ii> trace[maxN][maxK];
  21. pair<ii , ii> base = {{-1 , -1} , {-1 , -1}};
  22. int in[maxN] , sz[maxN] , DfsTime = 0 , pre[maxN];
  23.  
  24. void dfs_size(int u , int par){
  25.     in[u] = ++DfsTime;
  26.     for (auto e : g[u]){
  27.         int v = e.fi;
  28.         if (v != par){
  29.             sz[u]++;
  30.             dfs_size(v , u);
  31.         }
  32.     }
  33.     pre[in[u]] = sz[u];
  34. }
  35.  
  36. void init(){
  37.     for (int i = 1 ; i <= n ; i++){
  38.         pre[i] += pre[i - 1];
  39.     }
  40. }
  41.  
  42. int get(int u , int cnt){
  43.     int x = pre[in[u] - 1] + cnt + 1;
  44.     return x;
  45. }
  46.  
  47. ii sigma[maxN];
  48.  
  49. void dfs(int u , int par){
  50.     for (auto e : g[u]){
  51.         int v = e.fi;
  52.         if (v == par) continue;
  53.         dfs(v , u);
  54.     }
  55.     int cnt = 0;
  56.     for (auto e : g[u]){
  57.         int v = e.fi;
  58.         int w = e.se;
  59.         if (v == par) continue;
  60.         int idx = get(u , cnt); cnt++;
  61.         for (int x = 0 ; x <= k ; x++) tmp[x] = -inf;
  62.         //min(x , y + w) == y + w
  63.         for (int y = 0 ; y + w <= k ; y++){
  64.             int x = max(k - (y + w) , y + w);
  65.             if (tmp[y + w] < dp[u][x] + dp[v][y]){
  66.                 tmp[y + w] = dp[u][x] + dp[v][y];
  67.                 trace[idx][y + w] = {{u , x} , {v , y}};
  68.             }
  69.         }
  70.         //min(x , y + w) == x
  71.         for (int x = 0 ; x <= k ; x++){
  72.             int y = max(max(k - x , x) - w , 0);
  73.             if (tmp[x] < dp[u][x] + dp[v][y]){
  74.                 tmp[x] = dp[u][x] + dp[v][y];
  75.                 trace[idx][x] = {{u , x} , {v , y}};
  76.             }
  77.         }
  78.         //
  79.         for (int x = 0 ; x <= k ; x++){
  80.             if (dp[u][x] > tmp[x]){
  81.                 trace[idx][x] = {{u , x} , {-1 , -1}};
  82.             }
  83.             else{
  84.                 dp[u][x] = tmp[x];
  85.             }
  86.             if (x >= w && dp[u][x] < dp[v][x - w]){
  87.                 dp[u][x] = dp[v][x - w];
  88.                 trace[idx][x] = {{-1 , -1} , {v , x - w}};
  89.             }
  90.         }
  91.         for (int x = k - 1 ; x >= 0 ; x--){
  92.             if (dp[u][x] < dp[u][x + 1]){
  93.                 trace[idx][x] = {{u , x + 1} , {-1 , -1}};
  94.                 dp[u][x] = dp[u][x + 1];
  95.             }
  96.         }
  97.     }
  98.     if (dp[u][0] < 1ll * c[u]){
  99.         dp[u][0] = 1ll * c[u];
  100.         if (sz[u] > 0){
  101.             trace[get(u , sz[u] - 1)][0] = base;
  102.         }
  103.     }
  104.     sigma[u] = {-1 , -1};
  105.     for (auto e : g[u]){
  106.         int v = e.fi;
  107.         int w = e.se;
  108.         if (v == par) continue;
  109.         if (DP[u] < DP[v]){
  110.             DP[u] = DP[v];
  111.             sigma[u] = {-1 , -1};
  112.         }
  113.         if (DP[u] < dp[v][k - w] + 1ll * c[u]){
  114.             DP[u] = dp[v][k - w] + 1ll * c[u];
  115.             sigma[u] = {v , k - w};
  116.         }
  117.     }
  118. }
  119.  
  120. vector<int> res;
  121.  
  122. void find_path(int u , int x , int cnt){
  123.     if (cnt < 0){
  124.         res.push_back(u);
  125.         return;
  126.     }
  127.     auto it = trace[get(u , cnt)][x];
  128.     if (it == base){
  129.         res.push_back(u);
  130.         return;
  131.     }
  132.     int v = it.se.fi;
  133.     int y = it.se.se;
  134.     if (v != -1){
  135.         find_path(v , y , sz[v] - 1);
  136.     }
  137.     int nxt_u = it.fi.fi;
  138.     int nxt_x = it.fi.se;
  139.     if (nxt_u == -1) return;
  140.     if (v != -1){
  141.         find_path(nxt_u , nxt_x , cnt - 1);
  142.     }
  143.     else{
  144.         if (nxt_x == x + 1){
  145.             find_path(nxt_u , nxt_x , cnt);
  146.         }
  147.         else{
  148.             find_path(nxt_u , nxt_x , cnt - 1);
  149.         }
  150.     }
  151. }
  152.  
  153. void solve(){
  154.     cin >> n >> k;
  155.     for (int i = 1 ; i <= n ; i++){
  156.         for (int x = 0 ; x <= k ; x++) dp[i][x] = -inf , trace[i][x] = base;
  157.     }
  158.     for (int i = 1 ; i <= n ; i++) cin >> c[i];
  159.     for (int i = 1 ; i < n ; i++){
  160.         int u , v , w;
  161.         cin >> u >> v >> w;
  162.         g[u].push_back({v , w});
  163.         g[v].push_back({u , w});
  164.     }
  165.     dfs_size(1 , 0);
  166.     init();
  167.     dfs(1 , 0);
  168.     if (dp[1][0] >= DP[1]){
  169.         find_path(1 , 0 , sz[1] - 1);
  170.     }
  171.     else{
  172.         for (int i = 1 ; i <= n ; i++){
  173.             if (DP[1] == DP[i] && sigma[i].fi != -1){
  174.                 int u = sigma[i].fi;
  175.                 int x = sigma[i].se;
  176.                 res.push_back(i);
  177.                 find_path(u , x , sz[u] - 1);
  178.                 break;
  179.             }
  180.         }
  181.     }
  182.     cout << max(dp[1][0] , DP[1]) << "\n";
  183.     cout << sz(res) << "\n";
  184.     for (int x : res) cout << x << " ";
  185. }
  186.  
  187. #define name "cay"
  188.  
  189. int main(){
  190.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  191.     if (fopen(name".INP" , "r")){
  192.         freopen(name".INP" , "r" , stdin);
  193.         freopen(name".OUT" , "w" , stdout);
  194.     }
  195.     int t = 1; cin >> t;
  196.     solve();
  197.     return 0;
  198. }
Success #stdin #stdout 0.01s 13844KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
1
1
https://ideone.com/olrDrZ
language:
C++14 (gcc 8.3)
created:
2 days 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!