#include <bits/stdc++.h>
#include "infection.h"
#include <vector>
#include <utility>
using namespace std;

const int MAXN = 160000;
vector<int> adj[MAXN];
vector<int> vrez;
char fr[MAXN];
int niv[MAXN], par[MAXN], vin[MAXN], vout[MAXN], jump[MAXN];
int time1;
void dfs(int nod) {
    int nr, i, x;
    time1++;
    vin[nod] = time1;
    x = jump[par[nod]];
    if (niv[x] - niv[jump[x]] == niv[par[nod]] - niv[x]) {
        jump[nod] = jump[x];
    } else {
        jump[nod] = par[nod];
    }
    //printf("nod = %d jump = %d par = %d\n", nod - 1, jump[nod] - 1, par[nod] - 1);
    nr = adj[nod].size();
    for (i = 0; i < nr; i++) {
        x = adj[nod][i];
        if (par[x] == -1) {
            par[x] = nod;
            niv[x] = niv[nod] + 1;
            dfs(x);
        }
    }
    vout[nod] = time1;
}
char verifStramos(int x, int y) {
    return (vin[x] <= vin[y] && vout[x] >= vout[y]);
}
int lca(int x, int y) {
    while (verifStramos(x, y) == 0) {
        if (jump[x] > 0 && verifStramos(jump[x], y) == 0) {
            x = jump[x];
        } else {
            x = par[x];
        }
    }
    return x;
}
int dist(int x, int y) {
    return niv[x] + niv[y] - 2 * niv[lca(x, y)];
}
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
) {
    //adun 1 la noduri
    int n, sum, i, x, y, m;
    n = R.size() + 1;
    m = D.size();
    for (i = 0; i < n - 1; i++) {
        x = R[i].first + 1;
        y = R[i].second + 1;
        //printf("x = %d y = %d\n", x, y);
        adj[x].push_back(y);
        adj[y].push_back(x);
        par[i + 2] = -1;
    }
    par[1] = 0;
    niv[1] = 1;
    time1 = 0;
    dfs(1);
    sum = 0;
    for (i = 0; i < m; i++) {
        fr[i] = I[i];
    }
    vrez.clear();
    for (i = 0; i < m; i++) {
        x = S[i] + 1;
        y = T[i] + 1;
        //printf("x = %d y = %d lca = %d\n", x, y, lca(x, y));
        vrez.push_back(fr[i] * (dist(x, y) + 1));
    }
    return vrez;
}

