Advertisement
a53

paths_sums

a53
May 19th, 2022
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.31 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using int64 = long long;
  5.  
  6. const int mod = 1e9 + 7;
  7. const int MAXN = 2e5 + 1;
  8. const int MAXM = MAXN << 1 | 1;
  9. const int LGMAX = 19;
  10. vector<pair<int,int>> G[MAXN];
  11. int M, tour[MAXM], first[MAXN], depth[MAXN], d[MAXN], sz[MAXN], dp[MAXN], pw2[20], rmq[MAXM][LGMAX], lg2[MAXM];
  12.  
  13. void dfs(int u, int p) {
  14. tour[++M] = u;
  15. first[u] = M;
  16. sz[u] = 1;
  17. for (auto it : G[u]) {
  18. int v;
  19. int64 w;
  20. tie(v, w) = it;
  21. if (v != p) {
  22. depth[v] = depth[u] + 1;
  23. d[v] = d[u] + w;
  24. if (d[v] >= mod)
  25. d[v] -= mod;
  26. dfs(v, u);
  27. int paths_sums = dp[v] + w * sz[v] % mod;
  28. if (paths_sums >= mod)
  29. paths_sums -= mod;
  30. dp[u] += paths_sums;
  31. if (dp[u] >= mod)
  32. dp[u] -= mod;
  33. sz[u] += sz[v];
  34. tour[++M] = u;
  35. }
  36. }
  37. }
  38.  
  39. void compute_rmq() {
  40. pw2[0] = 1;
  41. for (int i = 1; i <= M; ++i) {
  42. rmq[i][0] = tour[i];
  43. if (i < 20)
  44. pw2[i] = pw2[i - 1] << 1;
  45. if (i > 1)
  46. lg2[i] = lg2[i >> 1] + 1;
  47. }
  48. for (int j = 1; pw2[j] <= M; ++j)
  49. for (int i = 1; i + pw2[j] - 1 <= M; ++i) {
  50. int u = rmq[i][j - 1], v = rmq[i + pw2[j - 1]][j - 1];
  51. if (depth[u] < depth[v])
  52. rmq[i][j] = u;
  53. else rmq[i][j] = v;
  54. }
  55. }
  56.  
  57. int lca(int x, int y) {
  58. int l = first[x], r = first[y];
  59. if (l > r)
  60. swap(l, r);
  61. int diff = r - l + 1;
  62. int k = lg2[diff];
  63. int shift = diff - (1 << k);
  64. int u = rmq[l][k], v = rmq[l + shift][k];
  65. if (depth[u] < depth[v])
  66. return u;
  67. return v;
  68. }
  69.  
  70. int find_dist(int u, int v) {
  71. int ans = d[u] + d[v] - (d[lca(u, v)] << 1);
  72. while (ans < 0)
  73. ans += mod;
  74. if (ans >= mod)
  75. ans -= mod;
  76. return ans;
  77. }
  78.  
  79. int main() {
  80. ios_base::sync_with_stdio(false);
  81. cin.tie(nullptr);
  82. cout.tie(nullptr);
  83. int n, q;
  84. cin >> n >> q;
  85. for (int v = 2; v <= n; ++v) {
  86. int u, w;
  87. cin >> u >> w;
  88. G[u].emplace_back(v, w);
  89. }
  90. dfs(1, 0);
  91. compute_rmq();
  92. for (int i = 0; i < q; ++i) {
  93. int u, v;
  94. cin >> u >> v;
  95. int64 dist = find_dist(u, v);
  96. int ans = (int64)dp[u] * sz[v] % mod + dist * sz[u] % mod * sz[v] % mod;
  97. if (ans >= mod)
  98. ans -= mod;
  99. ans += (int64)dp[v] * sz[u] % mod;
  100. if (ans >= mod)
  101. ans -= mod;
  102. cout << ans << '\n';
  103. }
  104. return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement