#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

struct segtree
{
    struct node
    {
        ll val = INF, base = INF, diff = INF;
    };

    int n;
    vector<node>tree;

    segtree() = default;

    void upd(int ql, int qr, ll a, ll d)
    {
        upd(1,1,n,ql,qr,a,d);
    }

    ll query(int ql, int qr)
    {
        return query(1,1,n,ql,qr).val;
    }

    int walk(int val, int ql, int qr)
    {
        return walk(1,1,n,ql,qr,val);
    }

private:

    int walk(int v, int l, int r, int ql, int qr, ll val)
    {
        push(v,l,r);
        if(l>qr || r<ql || tree[v].val < val)
            return INF;

        if(l == r)
            return l;

        int mid = (l+r)/2;
        return min(walk(v*2,l,mid,ql,qr,val),
                   walk(v*2+1,mid+1,r,ql,qr,val));
    }


    void merge(node &ans, node &l, node&r)
    {
        ans.val = l.val + r.val;
    }

    ll sum(ll a, ll d, ll n)
    {
        if(a == INF || d == INF)
            return INF;
        return (2*a + (n-1) * d)/2 * n;
    }

    void push(int v, int l, int r)
    {
        ll base = tree[v].base, diff = tree[v].diff;
        if(base != INF && diff != INF)
        {
            ll len = r-l+1;
            ll newval = sum(base,diff,len);

            tree[v].val = min(tree[v].val,newval);
            if(l!=r)
            {
                int left = v*2,right = v*2+1,mid = (l+r)/2;
                tree[left].val = min(tree[left],sum(tree[left].base,tree[left].diff,mid-l+1));
                tree[right].val = min(tree[right], sum(tree[right].base,tree[right].diff,r-mid));

                if(l != mid)
                {
                    tree[left * 2].base = tree[left].base;
                    tree[left * 2].diff = tree[left].diff;
                    tree[left * 2 + 1].base = tree[left].base;
                    tree[left * 2 + 1].diff = tree[left].diff;
                }
                if((mid+1) != r)
                {
                    tree[right * 2].base = tree[right].base;
                    tree[right * 2].diff = tree[right].diff;
                    tree[right * 2 + 1].base = tree[right].base;
                    tree[right * 2 + 1].diff = tree[right].diff;

                }


                tree[left].base = tree[v].base;
                tree[left].diff = tree[v].diff;
                tree[right].base = tree[v].base;
                tree[right].diff = tree[v].diff;
            }
            tree[v].base = tree[v].diff = INF;

        }
    }

    void upd(int v, int l, int r, int ql, int qr, ll base, ll diff)
    {
        push(v,l,r);
        if(l>qr || r < ql)
            return;
        if(l>=ql && r<=qr)
        {
            tree[v].base = base;
            tree[v].diff = diff;
            push(v,l,r);
            return;
        }

        int mid = (l+r)/2;
        upd(v*2,l,mid,ql,qr,base,diff);
        upd(v*2+1,mid+1,r,ql,qr,base,diff);
        merge(tree[v],tree[v*2],tree[v*2+1]);
    }

    node query(int v, int l, int r, int ql, int qr)
    {
        push(v,l,r);
        if(l>qr || r<ql)
            return node();
        if(l>=ql && r<=qr)
            return tree[v];

        int mid = (l+r)/2;
        node ans;
        node left = query(v*2,l,mid,ql,qr);
        node right = query(v*2+1,mid+1,r,ql,qr);
        merge(ans,left,right);
        return ans;
    }

};

const int maxn = 5 + 3e5;
vector<int>edges[maxn];
int tin[maxn],tour[maxn], sz[maxn], depth[maxn], head[maxn], parent[maxn],timer = 0;
int st[20][maxn], lg[maxn];
segtree sg;

void build()
{
    for(int i=2; i<=timer; i++)
        lg[i] = lg[i/2] + 1;

    for(int i=1; i<=timer; i++)
        st[0][i] = tour[i];

    for(int i=1; i<=lg[timer]; i++)
        for(int j=1; j + (1<<i)<=timer; j++)
        {
            int left = st[i-1][j];
            int right = st[i-1][j + (1<<(i-1))];

            st[i][j] = (depth[left] < depth[right] ? left : right);
        }

}

int get_lca(int u, int v)
{
    int a = tin[u], b = tin[v];
    int i = lg[b-a+1];

    int left = st[i][a], right = st[i][b-(1<<i) + 1];
    return (depth[left] < depth[right] ? left : right);
}

ll get_dist(int u, int v)
{
    return depth[u] + depth[v] - 2 * depth[get_lca(u,v)];
}

void dfs_init(int u, int par)
{
    sz[u] = 1;
    tour[++timer] = u;
    tin[u] = timer;
    parent[u] = par;

    for(int v : edges[u])
    {
        if(v!=par)
        {
            depth[v] = depth[u] + 1;
            dfs_init(v,u);
        }
    }

    //tour[++timer] = u;
}

void dfs_heavy(int u, int par, int heavy)
{
    int heavy_sz = -1, heavy_child = -1;
    for(int v : edges[u])
        if(v!=par)
        {
            if(sz[v] > heavy_sz)
            {
                heavy_sz = sz[v];
                heavy_child = v;
            }
        }

    if(heavy_child != -1)
        dfs_heavy(heavy_child,u,heavy);

    head[u] = heavy;
    for(int v : edges[u])
        if(v!=par)
            dfs_heavy(v, u, v);
}

void update(int u, int v)
{
    // update with an increasing arithmetic progression from sv (start vertex) -> lca
    // update with a decreasing arithmetic progression from ev (end vertex) -> lca
    // 1 - increasing, -1 - decreasing

    int curr_left = 1 + get_dist(u,v), curr_right = 1, curr_upd = 1;
    while(head[u] != head[v])
    {
        if(depth[u] < depth[v])
        {
            swap(u,v);
            curr_upd *= -1;
        }


        if(curr_upd == -1)
        {
            // end -> lca
            sg.upd(tin[head[u]],tin[u],curr_left,-1);
            curr_left -= (depth[u] - depth[parent[head[u]]]);
            u = parent[head[u]];
        }
        else
        {
            // start -> lca
            sg.upd(tin[head[u]],tin[u],curr_right,+1);
            curr_right += (depth[u] - depth[parent[head[u]]]);
            u = parent[head[u]];
        }
    }

    // last update when it reduces to stick
    if(depth[u] < depth[v])
    {
        swap(u,v);
        curr_upd *= -1;
    }

    if(curr_upd == -1)
        sg.upd(tin[v], tin[u], curr_left, -1);
    else
        sg.upd(tin[v],tin[u], curr_right, +1);

}

int query(int u, int v, ll start_day)
{
    ll curr_day_left = start_day, curr_day_right = start_day + get_dist(u,v), ans = 0;
    int curr = 1; // start with right i.e. start -> lca
    while(head[u] != head[v])
    {
        if(depth[u] < depth[v])
        {
            swap(u,v);
            curr *= -1;
        }

        if(curr == 1)
        {
            int first_inf_day = sg.query(tin[head[u]],tin[u]);
            int first_inf_vert = sg.walk(first_inf_day, tin[head[u]],tin[u]);
            if(curr_day_left + (depth[u] - depth[first_inf_vert]) >= first_inf_day)
                ans = max(ans,get_dist(first_inf_vert,v) + 1);


            curr_day_left += (depth[parent[head[u]]] - depth[u]);
            u = parent[head[u]];
        }
        else
        {
            int first_inf_day = sg.query(tin[head[u]],tin[u]);
            int first_inf_vert = sg.walk(first_inf_day, tin[head[u]],tin[u]);
            if(curr_day_right - (depth[u] - depth[first_inf_vert]) >= first_inf_day)
                ans = max(ans,get_dist(first_inf_vert,v) + 1);

            curr_day_right -= (depth[parent[head[u]]] - depth[u]);
            u = parent[head[u]];
        }
    }


    if(depth[u] < depth[v])
    {
        swap(u,v);
        curr *= -1;
    }

    if(curr == 1)
    {
        int first_inf_day = sg.query(tin[u],tin[v]);
        int first_inf_vert = sg.walk(first_inf_day, tin[u],tin[v]);
        if(curr_day_left + (depth[u] - depth[first_inf_vert]) >= first_inf_day)
            ans = max(ans,get_dist(first_inf_vert,v) + 1);

    }
    else
    {
        int first_inf_day = sg.query(tin[u],tin[v]);
        int first_inf_vert = sg.walk(first_inf_day, tin[u],tin[v]);
        if(curr_day_right - (depth[u] - depth[first_inf_vert]) >= first_inf_day)
            ans = max(ans,get_dist(first_inf_vert,v) + 1);
    }


}

vector<int> solve(
    vector<std::pair<int, int>> R,
    vector<ll> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I
)
{

    for(auto [u,v] : R)
    {
        u++, v++;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    dfs_init(1,0);
    dfs_heavy(1,0,1);

    int n = D.size();
    for(int i=0; i<n; i++)
        update(S[i],T[i]);

    vector<int>ans(n);
    for(int i=0; i<n; i++)
    {
        ans[i] = query(S[i],T[i],D[i]);
    }

    return ans;

}
