Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using int64 = long long;
- const int mod = 1e9 + 7;
- const int MAXN = 2e5 + 1;
- const int MAXM = MAXN << 1 | 1;
- const int LGMAX = 19;
- vector<pair<int,int>> G[MAXN];
- int M, tour[MAXM], first[MAXN], depth[MAXN], d[MAXN], sz[MAXN], dp[MAXN], pw2[20], rmq[MAXM][LGMAX], lg2[MAXM];
- void dfs(int u, int p) {
- tour[++M] = u;
- first[u] = M;
- sz[u] = 1;
- for (auto it : G[u]) {
- int v;
- int64 w;
- tie(v, w) = it;
- if (v != p) {
- depth[v] = depth[u] + 1;
- d[v] = d[u] + w;
- if (d[v] >= mod)
- d[v] -= mod;
- dfs(v, u);
- int paths_sums = dp[v] + w * sz[v] % mod;
- if (paths_sums >= mod)
- paths_sums -= mod;
- dp[u] += paths_sums;
- if (dp[u] >= mod)
- dp[u] -= mod;
- sz[u] += sz[v];
- tour[++M] = u;
- }
- }
- }
- void compute_rmq() {
- pw2[0] = 1;
- for (int i = 1; i <= M; ++i) {
- rmq[i][0] = tour[i];
- if (i < 20)
- pw2[i] = pw2[i - 1] << 1;
- if (i > 1)
- lg2[i] = lg2[i >> 1] + 1;
- }
- for (int j = 1; pw2[j] <= M; ++j)
- for (int i = 1; i + pw2[j] - 1 <= M; ++i) {
- int u = rmq[i][j - 1], v = rmq[i + pw2[j - 1]][j - 1];
- if (depth[u] < depth[v])
- rmq[i][j] = u;
- else rmq[i][j] = v;
- }
- }
- int lca(int x, int y) {
- int l = first[x], r = first[y];
- if (l > r)
- swap(l, r);
- int diff = r - l + 1;
- int k = lg2[diff];
- int shift = diff - (1 << k);
- int u = rmq[l][k], v = rmq[l + shift][k];
- if (depth[u] < depth[v])
- return u;
- return v;
- }
- int find_dist(int u, int v) {
- int ans = d[u] + d[v] - (d[lca(u, v)] << 1);
- while (ans < 0)
- ans += mod;
- if (ans >= mod)
- ans -= mod;
- return ans;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int n, q;
- cin >> n >> q;
- for (int v = 2; v <= n; ++v) {
- int u, w;
- cin >> u >> w;
- G[u].emplace_back(v, w);
- }
- dfs(1, 0);
- compute_rmq();
- for (int i = 0; i < q; ++i) {
- int u, v;
- cin >> u >> v;
- int64 dist = find_dist(u, v);
- int ans = (int64)dp[u] * sz[v] % mod + dist * sz[u] % mod * sz[v] % mod;
- if (ans >= mod)
- ans -= mod;
- ans += (int64)dp[v] * sz[u] % mod;
- if (ans >= mod)
- ans -= mod;
- cout << ans << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement