#include <bits/stdc++.h>

using namespace std;

const int N = 151000;
const int LOGN = 21;

int jmp[N][LOGN], depth[N], n;
vector<int> g[N];

void dfs(int v, int p = -1) {
    jmp[v][0] = (p == -1 ? v : p);
    for (int k = 1; k < LOGN; k++)
        jmp[v][k] = jmp[jmp[v][k - 1]][k - 1];
    depth[v] = (p == -1 ? 0 : depth[p] + 1);
    for (int u : g[v]) if (u != p)
        dfs(u, v);
}

int lca(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    for (int k = LOGN - 1; k >= 0; k--)
        if (depth[v] - (1 << k) >= depth[u])
            v = jmp[v][k];
    if (u == v) return u;
    for (int k = LOGN - 1; k >= 0; k--)
        if (jmp[v][k] != jmp[u][k]) {
            v = jmp[v][k];
            u = jmp[u][k];
        }
    return jmp[v][0];
}

vector<int> solve(vector<pair<int, int>> R, vector<long long> D, vector<int> S, vector<int> T, vector<bool> I) {
    n = (int) R.size() + 1;
    for (int i = 0; i < n - 1; i++) {
        g[R[i].first].push_back(R[i].second);
        g[R[i].second].push_back(R[i].first);
    }
    dfs(0);
    vector<int> ans;
    int m = (int) D.size();
    for (int i = 0; i < m; i++) {
        int u = S[i];
        int v = T[i];
        int l = lca(u, v);
        ans.push_back(I[i] * (depth[u] + depth[v] - 2 * depth[l] + 1));
    }
    return ans;
}
