#include "infection.h"
#include <vector>
#include <utility>
#include<iostream>
#include<map>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
using ll = long long;
#define V vector
#define VI V<int>
#define rep(i,a,b,step) for(int i=int(a);i<=int(b);i+=int(step))
#define repl(i,a,b,step) for(int i=int(a);i>=int(b);i-=int(step))
#define ff first
#define ss second
#define pq priority_queue
#define pb push_back
const ll inf = 1e18;
const int N = 1e5 + 5e4;
VI graph[N];
int t = 0, tin[N], tout[N], up[N][20], d[N];
//bool dfs1(int u, int t, int p, V<bool>&mark) {
//    if (u == t) {
//        mark[u] = 1;
//        return 1;
//    }
//    for (auto& i : graph[u])if (i != p and dfs1(i, t, u, mark)) {
//        mark[u] = 1;
//        return 1;
//    }
//    return 0;
//}
void dfs(int u, int p) {
    tin[u] = ++t;
    up[u][0] = p;
    rep(i, 1, 19, 1)up[u][i] = up[up[u][i - 1]][i - 1];
    for (auto& i : graph[u])if (i != p)
        d[i] = d[u] + 1, dfs(i, u);
    tout[u] = t;
}
bool ok(int u, int v) {
    return tin[u] <= tin[v] and tout[u] >= tout[v];
}
int lca(int u, int v) {
    if (ok(u, v))return u;
    if (ok(v, u))return v;
    repl(i, 19, 0, 1)if (!ok(up[u][i], v))
        u = up[u][i];
    return up[u][0];
}
int dist(int u, int v) {
    return d[u] + d[v] - d[lca(u, v)] * 2 + 1;
}
std::vector<int> solve(
    std::vector<std::pair<int, int>> R,
    std::vector<long long> D,
    std::vector<int> S,
    std::vector<int> T,
    std::vector<bool> I
) {
    int n = R.size() + 1, m = D.size();
  /*  V<ll>ds(m, inf);
    pq<pair<ll, int>, V<pair<ll, int>>, greater<>>q;
    vector<int>ans(m);
    V<V<bool>>mark(m, V<bool>(n));
    rep(i, 0, n - 2, 1) {
        graph[R[i].ff].pb(R[i].ss);
        graph[R[i].ss].pb(R[i].ff);
    }
    rep(i, 0, m - 1, 1) {
        if (I[i]) {
            ds[i] = D[i];
            q.push({ ds[i],i });
        }
        dfs1(S[i], T[i], -1, mark[i]);
    }
    pair<ll, int>cur;
    ll d;
    while (!q.empty()) {
        cur = q.top();
        q.pop();
        d = cur.ff;
        u = cur.ss;
        rep(i, 0, m - 1, 1) {

        }
    }*/
    rep(i, 0, n - 2, 1) {
        graph[R[i].ff].pb(R[i].ss);
        graph[R[i].ss].pb(R[i].ff);
    }
    dfs(0, 0);
    VI ans(m);
    rep(i, 0, m - 1, 1)ans[i] = dist(S[i], T[i]) * I[i];
    return ans;
}