#include "bits/stdc++.h"
#include "infection.h"
// #include "grader.cpp"

using namespace std;

#define SZ(s) (int)s.size()
#define ff first
#define ss second
#define ll long long

const int N = 150005;

vector <int> v[N];

int sp[N][20], dep[N];

void dfs(int x, int y) {
    sp[x][0] = y;
    dep[x] = dep[y] + 1;
    for(auto i : v[x]) {
        if(i == y) continue;
        dfs(i, x);
    }
}

int lca(int x, int y) {
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = 19; i >= 0; i--) {
        if(dep[sp[x][i]] >= dep[y]) x = sp[x][i];
    }
    if(x == y) return x;
    for(int i = 19; i >= 0; i--) {
        if(sp[x][i] != sp[y][i]) {
            x = sp[x][i];
            y = sp[y][i];
        }
    }
    return sp[x][0];
}

int ds(int x, int y) {
    return (dep[x] + dep[y] - 2 * dep[lca(x, y)]);
}

vector<int> solve(
    vector<pair<int, int>> R,
    vector<ll> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I) {
    int n = SZ(R) + 1;
    for(int i = 0; i < n-1; i++) {
        R[i].ff++;
        R[i].ss++;
        v[R[i].ff].push_back(R[i].ss);
        v[R[i].ss].push_back(R[i].ff);
    }
    dfs(1, 0);
    for(int j = 1; j < 20; j++) {
        for(int i = 1; i <= n; i++) {
            sp[i][j] = sp[sp[i][j-1]][j-1];
        }
    }
    int m = SZ(D);
    vector <int> ans;
    for(int i = 0; i < m; i++) {
        S[i]++;
        T[i]++;
        ans.push_back((ds(S[i], T[i])+1) * I[i]);
    }
    return ans;
}
