fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. using vi = vector<int>;
  6. using pi = pair<int, int>;
  7. using vl = vector<ll>;
  8. #define iter(x) begin(x), end(x)
  9. const int N = 3e5 + 5;
  10. vi e[N];
  11. ll a[N], b[N];
  12. int root[N];
  13. int find(int k){
  14.     return root[k] == -1 ? k : (root[k] = find(root[k]));
  15. }
  16. ll dp[N][3]; // 0 = dist+0, 1 = dist+1, 2 = dist-1; 
  17. vi aux[N];
  18. ll depth[N];
  19. int par[N];
  20. ll weight_m1[N];
  21. void build(int k, int p=-1){
  22.     dp[k][0] = a[k] - b[k] * (depth[k] + 1);
  23.     dp[k][2] = -1e18;
  24.     weight_m1[k] = a[k] - b[k] * (depth[k] - 1);
  25.     par[k] = p;
  26.     for(int j : e[k]){
  27.         if(j == p) continue;
  28.         depth[j] = depth[k] + 1;
  29.         build(j, k);
  30.         dp[k][0] = max(dp[k][0], dp[j][0]);
  31.         weight_m1[k] = max(weight_m1[k], weight_m1[j]);
  32.     }
  33. }
  34. int n,m;
  35. void push_all(){
  36.     vi all(n);
  37.     iota(iter(all), 1);
  38.     sort(iter(all), [&](int a, int b){
  39.         return depth[a] > depth[b];
  40.     });
  41.     for(int k : all){
  42.         for(int j : aux[k]){
  43.             if(depth[j] < depth[k]){
  44.                 dp[k][0] = max(dp[k][0], dp[j][0]);
  45.                 dp[k][2] = max(dp[k][2], dp[j][2]);
  46.             }
  47.         }
  48.         for(int j : aux[k]){
  49.             if(depth[j] == depth[k]){
  50.                 dp[k][2] = max(dp[k][2], weight_m1[j]);
  51.             }
  52.         }
  53.     }
  54. }
  55. int main() {
  56.     ios::sync_with_stdio(false); cin.tie(0); 
  57.     memset(root, -1, sizeof root);
  58.     cin >> n >> m;
  59.     for(int i = 1; i <= n; i++){
  60.         cin >> a[i] >> b[i];
  61.     }
  62.     for(int i = 1; i < n; i++){
  63.         int u,v;
  64.         cin >> u >> v;
  65.         int ru = find(u), rv = find(rv);
  66.         if(ru != rv){
  67.             e[u].push_back(v);
  68.             e[v].push_back(u);
  69.         }else{
  70.             aux[u].push_back(v);
  71.             aux[v].push_back(u);
  72.         }
  73.     }
  74.     build(1);
  75.     push_all();
  76.     for(int i = 1; i <= n; i++){
  77.         cout << i << ' ' << dp[i][0] << ' ' << dp[i][2] << endl;
  78.         if(depth[i] == 1) { // connected to 1
  79.             ll ans = max(dp[i][0], dp[i][2]);
  80.             // cout << ans << '\n';
  81.         }   
  82.     }
  83. }
  84.  
Success #stdin #stdout 0.01s 26264KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/lJYRHK
language:
C++ (gcc 8.3)
created:
8 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!