fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 1e5;
  9. const int maxlog = 18;
  10.  
  11. struct Query
  12. {
  13.     int id, x, y, mobius;
  14. };
  15. struct Edge
  16. {
  17.     int x, c, d;
  18. };
  19.  
  20. int n, q, beg[maxn + 10], fin[maxn + 10], par[maxn + 10][maxlog + 2], timer = 0;
  21. ll cnt[maxn + 10], sum[maxn + 10], ans[maxn + 10], dist[maxn + 10];
  22. vector<Edge> adj[maxn + 10];
  23. vector<Query> query[maxn + 10];
  24.  
  25. void precompute(int top, int p = -1)
  26. {
  27.     beg[top] = ++timer;
  28.     for (Edge e : adj[top])
  29.     {
  30.         int next_top = e.x;
  31.         int w = e.d;
  32.         if (next_top == p) continue;
  33.         dist[next_top] = dist[top] + w;
  34.         par[next_top][0] = top;
  35.         precompute(next_top, top);
  36.     }
  37.     fin[top] = timer;
  38. }
  39. bool is_inside(int x, int y)
  40. {
  41.     if (!x) return 1;
  42.     return beg[x] <= beg[y] && fin[y] <= fin[x];
  43. }
  44. int getLCA(int x, int y)
  45. {
  46.     if (is_inside(x, y)) return x;
  47.     if (is_inside(y, x)) return y;
  48.     for (int i = maxlog; i >= 0; i--)
  49.         if (!is_inside(par[x][i], y))
  50.             x = par[x][i];
  51.     return par[x][0];
  52. }
  53. void dfs(int top, int par = -1)
  54. {
  55.     for (Query ask : query[top])
  56.     {
  57.         int id = ask.id;
  58.         int x = ask.x;
  59.         int y = ask.y;
  60.         int mobious = ask.mobius;
  61.         ans[id] += (cnt[x] * y - sum[x]) * mobious;
  62.     }
  63.     for (Edge e : adj[top])
  64.     {
  65.         int next_top = e.x;
  66.         int c = e.c;
  67.         int w = e.d;
  68.         if (next_top == par) continue;
  69.         cnt[c]++;
  70.         sum[c] += w;
  71.         dfs(next_top, top);
  72.         cnt[c]--;
  73.         sum[c] -= w;
  74.     }
  75. }
  76.  
  77. int main()
  78. {
  79.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  80.     if (fopen("COLORFUL_TREE.INP", "r"))
  81.     {
  82.         freopen("COLORFUL_TREE.INP", "r", stdin);
  83.         freopen("COLORFUL_TREE.OUT", "w", stdout);
  84.     }
  85.  
  86.     cin >> n >> q;
  87.     for (int i = 1; i < n; i++)
  88.     {
  89.         int x, y, c, d;
  90.         cin >> x >> y >> c >> d;
  91.         adj[x].push_back({y, c, d});
  92.         adj[y].push_back({x, c, d});
  93.     }
  94.     precompute(1);
  95.     for (int j = 1; j <= maxlog; j++)
  96.         for (int i = 1; i <= n; i++)
  97.             par[i][j] = par[par[i][j - 1]][j - 1];
  98.     for (int i = 1; i <= q; i++)
  99.     {
  100.         int x, y, u, v;
  101.         cin >> x >> y >> u >> v;
  102.         int lca = getLCA(u, v);
  103.         ans[i] = dist[u] + dist[v] - 2 * dist[lca];
  104.         query[u].push_back({i, x, y, 1});
  105.         query[v].push_back({i, x, y, 1});
  106.         query[lca].push_back({i, x, y, -2});
  107.     }
  108.     dfs(1);
  109.     for (int i = 1; i <= q; i++)
  110.         cout << ans[i], el;
  111. }
Success #stdin #stdout 0.01s 9956KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/L86LXT
language:
C++14 (gcc 8.3)
created:
8 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!