#include <bits/stdc++.h>

using namespace std;

const int logN = 18;

vector<int> solve(vector<pair<int, int>> edges, vector<long long> d, vector<int> s, vector<int> t, vector<bool> infected) {
    int n = edges.size() + 1, m = d.size();

    cerr << n << ' ' << m << "\n";

    vector<vector<int>> tree(n);
    for (auto &[u, v] : edges) {
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    vector<int> tin(n), tout(n), depth(n);
    vector<vector<int>> up(logN, vector<int>(n, -1));
    int timer = 0;

    function<void(int)> dfs = [&](int v) {
        tin[v] = timer++;

        for (int &u : tree[v]) {
            if (u != up[0][v]) {
                up[0][u] = v;
                depth[u] = depth[v] + 1;
                dfs(u);
            }
        }

        tout[v] = timer;
    };

    dfs(0);

    auto isAnc = [&](int u, int v) {
        return tin[u] <= tin[v] && tout[v] <= tout[u];
    };

    auto lca = [&](int u, int v) {
        if (isAnc(u, v))
            return u;

        if (isAnc(v, u))
            return v;

        for (int i = logN - 1; i >= 0; i--) {
            if (up[i][u] != -1 && !isAnc(up[i][u], v))
                u = up[i][u];
        }

        return up[0][u];
    };

    auto dist = [&](int u, int v) {
        return depth[u] + depth[v] - 2 * depth[lca(u, v)] + 1;
    };

    vector<int> ans(m);
    for (int i = 0; i < m; i++)
        ans[i] = dist(s[i], t[i]) * infected[i];

    return ans;
}