#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int MAXN = 150000 + 5;

vector<vector<int>> adj;

int n, m;
int lift[20][MAXN];
int depth[MAXN];

void dfs(int u, int p)
{
    lift[0][u] = p;
    // cerr << u << '\n';
    for(int v : adj[u])
    {
        if(v == p)
            continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

int get_anc(int u, int d)
{
    for(int j = 0; j < 20 ;j++)
    {
        if((d >> j) & 1)
        {
            u = lift[j][u];
        }
    }
    return u;
}

int get_lca(int u, int v)
{
    if(depth[u] < depth[v])
        swap(u, v);
    u = get_anc(u, depth[u] - depth[v]);
    if(u == v)
        return u;
    for(int i = 19; i >= 0; i--)
    {
        if(lift[i][u] != lift[i][v])
        {
            u = lift[i][u];
            v = lift[i][v];
        }
    }
    return lift[0][u];
}


vector<int> act;
vector<int> st, dr;
vector<vector<int>> path;
vector<int> inff;

int gimme_pos(int i, int tm)
{
    return path[i][tm - st[i]];
}

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
)
{
    n = R.size() + 1;
    m = S.size();
    adj.clear();
    adj.resize(n);
    act.clear();
    act.resize(n);
    for(auto [u, v] : R)
    {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(0, -1);
    for(int i = 1; i < 20; i++)
    {
        for(int j = 0; j < n; j++)
        {
            lift[i][j] = lift[i - 1][lift[i - 1][j]];
        }
    }
    vector<int> ans;
    path.clear();
    path.resize(m);
    vector<int> tm;
    map<int, vector<int>> sts;
    inff.clear();
    inff.resize(m);
    st.clear();
    st.resize(m);
    dr.clear();
    dr.resize(m);
    for(int i = 0; i < m; i++)
    {
        // cerr << "D" << S[i] << ' ' << T[i] << '\n';
        vector<int> aux;
        int w = get_lca(S[i], T[i]);
        int u = S[i], v = T[i];
        while(v != w)
        {
            path[i].push_back(v);
            v = lift[0][v];
        }
        path[i].push_back(w);
        while(u != w)
        {
            aux.push_back(u);
            u = lift[0][u];
        }
        reverse(aux.begin(), aux.end());
        for(int x : aux)
            path[i].push_back(x);
        reverse(path[i].begin(), path[i].end());
        int dist = depth[S[i]] + depth[T[i]] - 2 * depth[w] + 1;
        for(int i = D[i]; i <= D[i] + dist; i++)
        {
            tm.push_back(i);
        }
        st[i] = D[i];
        dr[i] = D[i] + dist - 1;
        inff[i] = 1e9;
        sts[st[i]].push_back(i);
        // cerr << S[i] << ' ' << T[i] << ' ' << w << '\n';
        // if(I[i])
        //     ans.push_back(dist);
        // else
        //     ans.push_back(0);
    }
    sort(tm.begin(), tm.end());
    tm.erase(unique(tm.begin(), tm.end()), tm.end());
    act.clear();
    act.resize(n);
    // for(int j = 0; j < m ;j ++)
    // {
    //     cerr << j << '\n';
    //     for(int x : path[j])
    //         cerr << x << ' ';
    //     cerr << '\n';
    // }
    // return {};
    set<int> ons;
    for(int i = 0; i < tm.size(); i++)
    {
        int t = tm[i];
        for(int j = 0; j < m; j++)
        {
            if(st[j] <= t && t <= dr[j])
            {
                cerr << "LL" << j << ' ' << gimme_pos(j, t) << '\n';
                if(I[j])
                    act[gimme_pos(j, t)] = true;
            }
        }
        for(int j = 0; j < m; j++)
        {
            if(st[j] <= t && t <= dr[j])
            {
                // cerr << "D" << j << ' ' << t << ' ' << gimme_pos(j, t) << '\n';
                if(act[gimme_pos(j, t)])
                {
                    I[j] = true;
                    // cerr << j << ' ' << t << ' ' << gimme_pos(j, t) << '\n';
                    inff[j] = min(inff[j], t);
                }
            }
        }
        for(int j = 0; j < m; j++)
        {
            if(st[j] <= t && t <= dr[j])
            {
                act[gimme_pos(j, t)] = false;
            }
        }
        continue;
        // int t1 = tm[i], t0 = -10;
        // for(int x : sts[t1])
        //     ons.insert(x);
        // return {};
        // vector<int> bdss;
        // for(int x : ons)
        // {
        //     if(t1 > dr[x])
        //     {
        //         bdss.push_back(x);
        //     }
        // }
        // for(int x : bdss)
        //     sts.erase(x);
        // // for(int x : ons)
        // // {
        // //     cerr << x << ' ';
        // // }
        // // cerr << '\n';
        // for(int x : ons)
        // {
        //     if(I[x])
        //     {
        //         act[gimme_pos(x, t1)] = true;
        //     }
        // }
        // for(int x : ons)
        // {
        //     if(act[gimme_pos(x, t1)])
        //     {
        //         inff[x] = min(inff[x], t1);
        //     }
        // }
        // for(int x : ons)
        // {
        //     act[gimme_pos(x, t1)] = false;
        // }
    }
    for(int i = 0; i < m; i++)
    {
        ans.push_back(max(0, dr[i] - inff[i] + 1));
    }
    return ans;
}