1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

const ll MOD = 1e9 + 7;
ll norm(ll x) {
    x %= MOD;
    if (x < 0) x += MOD;
    return x;
}
class TreeAncestor {
    vector<int> depth;       // 深度
    vector<vector<int>> pa;  // 2^i祖先

public:
    TreeAncestor(vector<vector<int>>& edges) {  // 直接传边数组
        int n = edges.size() + 1;
        int m = bit_width(unsigned(n));
        vector<vector<int>> ma(n);  // 这里还是0-based
        for (auto& p : edges) {
            int x = p[0], y = p[1];
            ma[x].push_back(y);
            ma[y].push_back(x);
        }
        depth.resize(n);
        pa.resize(n, vector<int>(m, -1));
        auto dfs = [&](auto&& self, int x, int fa) -> void {
            pa[x][0] = fa;
            for (int y : ma[x]) {
                if (y == fa) continue;
                depth[y] = depth[x] + 1;
                self(self, y, x);
            }
            return;
        };  // 预处理深度
        dfs(dfs, 0, -1);
        for (int i = 0; i < m - 1; i++) {
            for (int x = 0; x < n; x++) {
                if (pa[x][i] == -1) continue;
                pa[x][i + 1] = pa[pa[x][i]][i];
            }
        }  // 预处理2^i祖先
    }

    int get_depth(int x) { return depth[x]; }  // 获取某个点的深度

    int get_kth_ancestor(int node, int k) {
        for (int x = k; node != -1 && x > 0; x -= lowbit(x)) {
            node = pa[node][countr_zero((unsigned)x)];
        }
        return node;
    }  // 得到第k个祖先，类似树状数组的倍增

    int get_lca(int x, int y) {
        if (depth[x] > depth[y]) swap(x, y);
        y = get_kth_ancestor(y, depth[y] - depth[x]);  // 先跳到深度相同
        if (x == y) return x;
        for (int i = pa[x].size() - 1; i >= 0; i--) {
            int px = pa[x][i], py = pa[y][i];
            if (px != py) {
                x = px, y = py;
            }  // 倍增跳
        }
        return pa[x][0];
    }  // 得到最近公共祖先
};
void solve() {
    int n, x, y, z, q;
    cin >> n;
    vi a(n, -1);
    vector<vector<pii>> ma(n);
    vvi edges;
    rep(i, 1, n - 1) {
        cin >> x >> y >> z;
        ma[x - 1].emplace_back(y - 1, z);
        ma[y - 1].emplace_back(x - 1, z);
        edges.push_back({x - 1, y - 1});
    }
    TreeAncestor ta(edges);
    vl siz(n);
    vl dis(n);
    vl down1(n);
    vl down2(n);
    vl all1(n);
    vl all2(n);
    auto calc = [&](int x, int y) -> ll { return norm(dis[x] + dis[y] - 2LL * dis[ta.get_lca(x, y)]); };
    auto is_ancestor = [&](int x, int y) -> bool { return ta.get_lca(x, y) == x; };
    auto dfs = [&](this auto&& dfs, int x, int pa) -> void {
        siz[x] = 1, down1[x] = 0, down2[x] = 0;
        for (auto& [y, z] : ma[x]) {
            if (y == pa) continue;
            dis[y] = norm(dis[x] + z);
            dfs(y, x);
            siz[x] += siz[y];
            down1[x] = norm(down1[x] + down1[y] + siz[y] * z % MOD);
            down2[x] = norm(down2[x] + down2[y] + 2LL * z * down1[y] + siz[y] * z % MOD * z % MOD);
        }
    };
    dfs(0, -1);
    all1[0] = down1[0], all2[0] = down2[0];
    auto dfs2 = [&](this auto&& dfs2, int x, int pa) -> void {
        for (auto& [y, z] : ma[x]) {
            if (y == pa) continue;
            ll tem = norm(down1[y] + siz[y] * z % MOD);
            all1[y] = norm(all1[x] + norm(n - 2LL * siz[y]) * z % MOD);
            all2[y] = norm(all2[x] + 2LL * z % MOD * all1[x] % MOD - 4LL * z % MOD * tem % MOD + 1LL * n * z % MOD * z % MOD);
            dfs2(y, x);
        }
        return;
    };
    dfs2(0, -1);
    cin >> q;
    rep(i, 0, q - 1) {
        cin >> x >> y;
        x--, y--;
        ll tem = calc(x, y);
        ll ans = 0;
        if (is_ancestor(y, x)) {
            ans = norm(all2[x] - 2LL * ((n - siz[y]) * tem % MOD * tem % MOD + 2LL * tem % MOD * norm(all1[y] - down1[y]) +
                                        norm(all2[y] - down2[y])));
        } else {
            ans = norm(2LL * norm(siz[y] * tem % MOD * tem % MOD + 2LL * tem % MOD * down1[y] % MOD + down2[y]) - all2[x]);
        }
        cout << ans << endl;
    }
    return;
}