fork download
copy 
  1. /* AUTHOR: TUAN ANH - BUI */
  2. // ~~ icebear ~~
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. typedef pair<int, int> ii;
  8. typedef pair<int, ii> iii;
  9.  
  10. template<class X, class Y>
  11.     bool minimize(X &x, const Y &y) {
  12.         if (x > y) return x = y, true;
  13.         return false;
  14.     }
  15.  
  16. template<class X, class Y>
  17.     bool maximize(X &x, const Y &y) {
  18.         if (x < y) return x = y, true;
  19.         return false;
  20.     }
  21.  
  22. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  23. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  24. #define REP(i, n) for(int i=0; i<(n); ++i)
  25. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  26. #define MASK(i) (1LL << (i))
  27. #define BIT(S, i) (((S) >> (i)) & 1)
  28. #define mp make_pair
  29. #define pb push_back
  30. #define fi first
  31. #define se second
  32. #define all(x) x.begin(), x.end()
  33. #define task "qtree"
  34. /*END OF TEMPLATE. ICEBEAR AND THE CAT WILL WIN VOI26 */
  35.  
  36. const int MOD = 1e9 + 7;
  37. const int inf = (int)1e9 + 27092008;
  38. const ll INF  = (ll)1e18 + 27092008;
  39. const int N = 1e5 + 5;
  40. const int Q = 5e5 + 5;
  41. int n, q, t, m;
  42. vector<int> G[N];
  43. int diff[N];
  44. ll f[N][10];
  45. int x[Q], y[Q], k[Q], minHigh[N << 1][20], pos[N], tour[N << 1], timer, ans, h[N];
  46.  
  47. void dfs(int u, int par) {
  48.     pos[u] = ++timer;
  49.     tour[timer] = u;
  50.     for(int v : G[u]) if (v != par) {
  51.         h[v] = h[u] + 1;
  52.         dfs(v, u);
  53.         tour[++timer] = u;
  54.     }
  55. }
  56.  
  57. void DFS(int u, int par) {
  58.     FOR(j, 0, m) f[u][j] = -inf;
  59.     f[u][0] = 0;
  60.     for(int v : G[u]) if (v != par) {
  61.         DFS(v, u);
  62.         diff[u] += diff[v];
  63.         FORR(k, m, 1) FORR(j, k - 1, 0)
  64.             maximize(f[u][k], f[u][j] + diff[v] + f[v][k - 1 - j]);
  65.     }
  66.     maximize(ans, f[u][m]);
  67. }
  68.  
  69. #define MIN_HIGH(x, y) (h[x] < h[y] ? x : y)
  70. int LCA(int u, int v) {
  71.     int l = pos[u], r = pos[v];
  72.     if (l > r) swap(l, r);
  73.     int k = __lg(r - l + 1);
  74.     return MIN_HIGH(minHigh[l][k], minHigh[r - MASK(k) + 1][k]);
  75. }
  76.  
  77. void init(void) {
  78.     cin >> n >> q >> t >> m;
  79.     FOR(i, 2, n) {
  80.         int u, v;
  81.         cin >> u >> v;
  82.         G[u].pb(v);
  83.         G[v].pb(u);
  84.     }
  85.     FOR(i, 1, q) cin >> x[i] >> y[i] >> k[i];
  86. }
  87.  
  88. void process(void) {
  89.     dfs(1, -1);
  90.     FOR(i, 1, timer) minHigh[i][0] = tour[i];
  91.     FOR(j, 1, 19) FOR(i, 1, timer - MASK(j) + 1)
  92.         minHigh[i][j] = MIN_HIGH(minHigh[i][j - 1], minHigh[i + MASK(j - 1)][j - 1]);
  93.     while(t--) {
  94.         int l, r;
  95.         cin >> l >> r;
  96.         FOR(i, l, r) {
  97.             diff[x[i]] += k[i];
  98.             diff[y[i]] += k[i];
  99.             diff[LCA(x[i], y[i])] -= 2 * k[i];
  100.         }
  101.         ans = -inf;
  102.         DFS(1, -1);
  103.         cout << ans << '\n';
  104.         FOR(i, 1, n) diff[i] = 0;
  105.     }
  106. }
  107.  
  108. int main() {
  109.     ios_base::sync_with_stdio(0);
  110.     cin.tie(0); cout.tie(0);
  111.     if (fopen(task".inp", "r")) {
  112.         freopen(task".inp", "r", stdin);
  113.         freopen(task".out", "w", stdout);
  114.     }
  115.     int tc = 1;
  116. //    cin >> tc;
  117.     while(tc--) {
  118.         init();
  119.         process();
  120.     }
  121.     return 0;
  122. }
  123.  
  124.  
Success #stdin #stdout 0.01s 9624KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dgVdgm
language:
C++14 (gcc 8.3)
created:
6 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!