#include <bits/stdc++.h>
using namespace std;
using ll = int;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
using vi = vector<int>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()

// struct prq{
//     priority_queue<pll,vpl,greater<pll>> cur, er;
//     prq(){}
//     void push(pll o){cur.push(o);}
//     void erase(pll o){er.push(o);}
//     void clean(){
//         while(cur.top()==er.top()){
//             cur.pop();er.pop();
//         }
//     }
//     pll top(){
//         clean();
//         return cur.top();
//     }
// };

// struct seg{
//     vll bl, vl;
//     ll n;
//     vector<prq> bs;
//     seg(){}
//     seg(ll m):n(1<<(32-__builtin_clz(m-1))){
//         bl = vll(n*2);
//         vl = vll(n, 1e16);
//         bs = vector<prq>(n);
//         for(ll i = n; i < n*2; ++i){bl[i]=i-n;bs[i-n].push({1e16,-1});}
//         for(ll i = n-1; i > 0; --i)bl[i]=bl[i*2];
//     }
//     ll cmp(ll a, ll b){
//         if(vl[a]>vl[b])return b;
//         return a;
//     }
//     void upd(ll i, ll v, ll j){
//         bs[i].push({v,j});
//         vl[i] = bs[i].top().f;
//         i+=n;
//         for(i/=2; i>0; i/=2){
//             bl[i] = cmp(bl[i*2],bl[i*2+1]);
//         }
//     }
//     void rem(ll i, ll v, ll j){
//         bs[i].erase({v,j});
//         vl[i] = bs[i].top().f;
//         i+=n;
//         for(i/=2; i>0; i/=2){
//             bl[i] = cmp(bl[i*2],bl[i*2+1]);
//         }
//     }
//     pll que(ll a, ll b){
//         ll ans = a;
//         for(a+=n,b+=n;a<=b;a/=2,b/=2){
//             if(a%2==1)ans = cmp(ans, bl[a++]);
//             if(b%2==0)ans = cmp(ans, bl[b--]);
//         }
//         return bs[a].top();
//     }
// };

// priority_queue<pair<pll,ll>,vector<pair<pll,ll>>,greater<pair<pll,ll>>> pq;
// vll ans;
// struct twoseg{
//     seg hr,hl,sr,sl;
//     ll n;
//     twoseg(ll m){
//         hr=hl=sr=sl=seg(m);
//         n = hl.n;
//     }
//     void ads(ll i, ll j, ll d, ll dir){
//         if(dir==0){
//             sl.upd(i, d+i, j);
//         }
//         else{
//             sr.upd(i,i-d,j);
//         }
//     }
//     void adh(ll i, ll j, ll d, ll dir){
//         if(dir==0){
//             hl.upd(i, d+i, j);
//         }
//         else{
//             hr.upd(i,i-d,j);
//         }
//     }
//     void remh(ll i, ll j, ll d, ll dir, ll t){
//         if(dir==0){
//             hl.rem(i, d+i, j);
//         }
//         else{
//             hr.rem(i,i-d,j);
//         }
//         if(dir==1){
//             auto o = sl.que(i,n-1);
//             ll mt = (i-d+o.f)/2;
//             if(mt>t)return;
//             ans[j]=mt-i+1;
//             pq.push({mt})
//         }
//         if(dir==1){
//             auto o = sr.que(i,n-1);
//             ll mt = (i+d+o.f)/2;
//             if(mt<t)return;
//             ans[j] = i-mt+1;
//         }
//     }
//     ll rems(ll i, ll j, ll d, ll dir, ll t){
//         if(dir==0){
//             hl.rem(i, d+i, j);
//         }
//         else{
//             hr.rem(i,i-d,j);
//         }
//         if(dir==1){
//             auto o = sl.que(i,n-1);
//             ll mt = (i-d+o.f)/2;
//             if(mt>t)return -1;
//             return mt+d;
//         }
//         if(dir==1){
//             auto o = sr.que(i,n-1);
//             ll mt = (i+d+o.f)/2;
//             if(mt<t)return -1;
//             return d-mt;
//         }
//     }
// };

vvl g;
void dfs(ll cur, ll pr, vll& path, ll& ch, ll tr){
    if(!ch)path.pb(cur);
    if(cur==tr)ch=1;
    for(ll i:g[cur]){
        if(i!=pr)dfs(i, cur, path, ch, tr);
    }
    if(!ch)path.pop_back();
}

vector<int> solve(vector<pair<int, int>> r,vll d,vi s,vi t,vector<bool> inf){
    ll n = r.size()+1,m=d.size();
    vi ans(m);
    g = vvl(n);
    for(ll i = 0; i < n-1; ++i){
        g[r[i].f].pb(r[i].s);
        g[r[i].s].pb(r[i].f);
    }
    vvl path(m);ll o;
    map<pll,vll> pq;
    for(ll i = 0; i < m; ++i){
        o=0;
        dfs(s[i],s[i],path[i],o,t[i]);
        for(ll j = 0; j < path[i].size(); ++j){
            pq[{d[i]+j,path[i][j]}].pb(i);
        }
        if(inf[i])ans[i]=path[i].size();
    }
    for(auto [a,b]:pq){
        o=0;
        for(ll i:b)if(ans[i]!=0)o=1;
        if(o){
            for(ll i:b){
                ans[i] = max<ll>(ans[i], path[i].size()-a.f+d[i]);
            }
        }
    }
    return ans;
}