fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define FNAME "qtree"
  6.  
  7. const int N = 1e5 + 5;
  8. const int LG = 20;
  9. const int M = 9;
  10.  
  11. struct Query {
  12.     int u, v;
  13.     int k;
  14.     int lca;
  15. };
  16.  
  17. int n, q, t, m;
  18. vector<pair<int,int>> adj[N];
  19. Query queries[N * 5];
  20. int depth[N];
  21. int up[LG][N];
  22. int p[N];
  23. int dp[N][M];
  24.  
  25. void Task() {
  26.     ios_base::sync_with_stdio(false);
  27.     cin.tie(0); cout.tie(0);
  28.     cout << fixed << setprecision(9);
  29.     if (fopen(FNAME".inp","r")) {
  30.         freopen(FNAME".inp","r",stdin);
  31.         freopen(FNAME".out","w",stdout);
  32.     }
  33. }
  34.  
  35. void DFS_LCA(int u, int par) {
  36.     for (auto e : adj[u]) {
  37.         int v = e.first;
  38.         if (v ^ par) {
  39.             up[0][v] = u;
  40.             depth[v] = depth[u] + 1;
  41.             DFS_LCA(v, u);
  42.         }
  43.     }
  44. }
  45.  
  46. void construct_LCA() {
  47.     for (int i = 1; i < LG; i++) {
  48.         for (int j = 1; j <= n; j++) {
  49.             up[i][j] = up[i - 1][up[i - 1][j]];
  50.         }
  51.     }
  52. }
  53.  
  54. int LCA(int u, int v) {
  55.     if (depth[u] < depth[v]) swap(u, v);
  56.     for (int i = LG - 1; i >= 0; i--) {
  57.         if (depth[u] - (1 << i) >= depth[v]) {
  58.             u = up[i][u];
  59.         }
  60.     }
  61.     if (u == v) return u;
  62.     for (int i = LG - 1; i >= 0; i--) {
  63.         if (up[i][u] != up[i][v]) {
  64.             u = up[i][u];
  65.             v = up[i][v];
  66.         }
  67.     }
  68.     return up[0][u];
  69. }
  70.  
  71. void DFS_calc(int u, int par) {
  72.     for (auto &e : adj[u]) {
  73.         if (e.first ^ par) {
  74.             DFS_calc(e.first, u);
  75.             e.second = p[e.first];
  76.             p[u] += p[e.first];
  77.         }
  78.     }
  79. }
  80.  
  81. void DFS_DP(int u, int par) {
  82.     for (auto e : adj[u]) {
  83.         int v = e.first;
  84.         int w = e.second;
  85.         if (v ^ par) {
  86.             DFS_DP(v, u);
  87.             for (int x = m; x >= 1; x--) {
  88.                 for (int y = 0; y < x; y++) {
  89.                     dp[u][x] = max(dp[u][x], dp[v][y] + dp[u][x - y - 1] + e.second);
  90.                 }
  91.             }
  92.         }
  93.     }
  94. }
  95.  
  96. void solve() {
  97.     memset(p, 0, sizeof(p));
  98.     int l, r;
  99.     cin >> l >> r;
  100.     for (int i = l; i <= r; i++) {
  101.         p[queries[i].u] += queries[i].k;
  102.         p[queries[i].v] += queries[i].k;
  103.         p[queries[i].lca] -= queries[i].k * 2;
  104.     }
  105.     DFS_calc(1, 1);
  106.     memset(dp, 0, sizeof(dp));
  107.     DFS_DP(1, 1);
  108.     int ans = 0;
  109.     for (int i = 1; i <= n; i++) ans = max(ans, dp[i][m]);
  110.     cout << ans << '\n';
  111. }
  112.  
  113. void Solve() {
  114.     //Your Code
  115.     cin >> n >> q >> t >> m;
  116.     for (int i = 1; i < n; i++) {
  117.         int u, v;
  118.         cin >> u >> v;
  119.         adj[u].push_back({v, 0});
  120.         adj[v].push_back({u, 0});
  121.     }
  122.     up[0][1] = 0;
  123.     depth[1] = 0;
  124.     DFS_LCA(1, 1);
  125.     construct_LCA();
  126.     for (int i = 1; i <= q; i++) {
  127.         cin >> queries[i].u >> queries[i].v >> queries[i].k;
  128.         queries[i].lca = LCA(queries[i].u, queries[i].v);
  129.     }
  130.     for (int i = 1; i <= t; i++) solve();
  131. }
  132.  
  133. int main() {
  134.     Task();
  135.     Solve();
  136.     return 37^37;
  137. }
  138.  
Success #stdin #stdout 0.01s 10888KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/b5oeoZ
language:
C++ (gcc 8.3)
created:
5 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!