#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int nmax = 150005;

int n, m, b[nmax][20], deep[nmax], fr[nmax];
vector<int> v[nmax];

void dfs(int node, int prev = 0)
{
    b[node][0] = prev; deep[node] = deep[prev] + 1;
    for(int i = 1; i <= 18; i++)
        b[node][i] = b[b[node][i - 1]][i - 1];

    for(auto x : v[node])
        if(x != prev) dfs(x, node);
}

int lca(int x, int y)
{
    if(deep[x] != deep[y])
    {
        if(deep[x] < deep[y]) swap(x, y);
        int dif = deep[x] - deep[y];

        for(int i = 0; i <= 18; i++)
            if((1<<i)&dif) x = b[x][i];
    }

    for(int i = 18; i >= 0; i--)
        if(b[x][i] != b[y][i]) x = b[x][i], y = b[y][i];

    return (x == y ? x : b[x][0]);
}

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

    for(auto x : r) {
        v[x.first + 1].push_back(x.second + 1);
        v[x.second + 1].push_back(x.first + 1);
    }
    for(int i = 0; i < m; i++) s[i]++, t[i]++;

    dfs(1);

    vector<queue<int>> q; vector<int> ans; ans.clear();
    long long mini = d[0], maxi = d[0];
    for(int i = 0; i < m; i++)
    {
        mini = min(mini, d[i]);
        maxi = max(maxi, d[i] + t[i] - s[i]);

        fr[s[i]] = ii[i];

        queue<int> aux; while(!aux.empty()) aux.pop();
        int dad = lca(s[i], t[i]); vector<int> idk; idk.clear();

        while(s[i] != dad) aux.push(s[i]), s[i] = b[s[i]][0];
        while(t[i] != dad) idk.push_back(t[i]), t[i] = b[t[i]][0];

        aux.push(dad);
        for(int i = idk.size() - 1; i >= 0; i--) aux.push(idk[i]);

        q.push_back(aux); ans.push_back(0);

        if(ii[i]) ans[i] = q[i].size();
    }

    return ans;
}