fork download
copy 
  1. //Goi f[v] là tổng lớn nhất khi kết thúc tại v
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5. #define pb push_back
  6. #define BIT(i) (1LL << i)
  7. const int MAXN = 2e5 + 7;
  8. int par[MAXN][30], mx[MAXN][30], n, k, h[MAXN];
  9. ll w[MAXN], f[MAXN];
  10. vector <int> a[MAXN];
  11. const ll inf = -1e18;
  12. void dfs(ll u){
  13.     for(int i = 1; i <= 20; i++){
  14.         par[u][i] = par[par[u][i - 1]][i - 1];
  15.         mx[u][i] = max(mx[u][i - 1], mx[par[u][i - 1]][i - 1]);
  16.     }
  17.     for(auto v : a[u]){
  18.         if(v == par[u][0]) continue;
  19.         par[v][0] = u;
  20.         mx[v][0] = w[v];
  21.         h[v] = h[u] + 1;
  22.         dfs(v);
  23.     }
  24. }
  25.  
  26.  
  27. int lca(int u, int v){
  28.     int ans = 0;
  29.     if(h[u] < h[v]) swap(u, v); 
  30.     int x = h[u] - h[v];
  31.     for(int i = 20; i >= 0; i--){
  32.         if(x >= BIT(i)){
  33.             ans = max(ans, mx[u][i]);
  34.             u = par[u][i];
  35.             x -= BIT(i);
  36.         }
  37.     }
  38.     if(u == v) return max(ans, mx[u][0]);
  39.  
  40.     int h_max = __lg(h[u]);
  41.  
  42.     for(int i = h_max; i >= 0; i--){
  43.         if(par[u][i] != par[v][i]){
  44.             ans = max({ans, mx[u][i], mx[v][i]});
  45.             u = par[u][i];
  46.             v = par[v][i];
  47.         }
  48.     }
  49.     return max({ans, mx[u][1], mx[v][1]});
  50. }
  51.  
  52.  
  53. int main(){
  54.     ios_base::sync_with_stdio(0);
  55.     cout.tie(0);
  56.     cin.tie(0);
  57.     freopen("ship.inp", "r", stdin);freopen("ship.out", "w", stdout);
  58.     cin >> n;
  59.  
  60.     //Lấy trọng số đỉnh (1)
  61.     a[0].pb(1);
  62.     a[1].pb(0);
  63.  
  64.     for(int i = 1; i <= n; i++) cin >> w[i];
  65.     for(int i = 1; i <= n - 1; i++){
  66.         int x, y;
  67.         cin >> x >> y;
  68.         a[x].pb(y);
  69.         a[y].pb(x);
  70.     }
  71.     dfs(0);
  72.  
  73.     cin >> k;
  74.     fill(f, f + 1 + n, inf);
  75.     f[1] = 0;
  76.     while(k--){
  77.         int u, v;
  78.         cin >> u >> v;
  79.         f[v] = max(f[v], f[u] + lca(u, v));
  80.     }
  81.     cout << *max_element(f + 1, f + 1 + n);
  82.  
  83. }
  84.  
Success #stdin #stdout 0.01s 10240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QLATT3
language:
C++14 (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!