#include <bits/stdc++.h>
#define ss second
#define ff first
#define en end
#define be begin
#define ve vector
#define pb push_back
#define ppb pop_back
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
ve<int>e[5000];
int d[5000],in[5000],on[5000];
long long vx[5000];
ve<pair<pair<long long,int>,int>>c;
int z=0;
void dfs(int v,int pr=-1){
    z++;
    in[v]=z;
    if (pr==-1) d[v]=1;
    else d[v]=d[pr]+1;
    for (auto g:e[v]){
        if (g==pr) continue;
        dfs(g,v);
    }
    on[v]=z;
}
int pred(int a,int b){
    if (in[a]<=in[b] && on[a]>=on[b]){
        return 1;
    }
    return 0;
}
void dfs1(int v,int z,long long l,int nm){
    c.pb({{l,v},nm});
    //cout<<v<<" "<<z<<endl;
    if (v==z){
        vx[nm]=l;
       // cout<<nm<<" "<<vx[nm]<<endl;
        return;
    }
    if (pred(v,z)==1){
        for (auto g:e[v])
            if (pred(g,z)==1 && pred(v,g)==1) dfs1(g,z,l+1,nm);
    }
    else {
        for (auto g:e[v])
            if (d[g]<d[v]) dfs1(g,z,l+1,nm);
    }
}
std::vector<int> solve(
    std::vector<std::pair<int, int>> r,
    std::vector<long long> t,
    std::vector<int> q,
    std::vector<int> w,
    std::vector<bool> lk
) {
  int m=q.size();
  int n=r.size()+1;
  for (int i=0; i<n-1; i++){
    e[r[i].ff].pb(r[i].ss);
    e[r[i].ss].pb(r[i].ff);
  }
  z=0;
  dfs(0);
  ve<long long>b(m,0);
  for (int i=0; i<m; i++){
    if (lk[i]==1) b[i]=t[i];
    else b[i]=-1;
    //cout<<b[i]<<endl;
    dfs1(q[i],w[i],t[i],i);
  }
  ve<int>sd;
  int qw=0;
  sort(c.be(),c.en());
  for (int i=0; i<c.size(); i++){
    if (i==0 || c[i-1].ff.ff!=c[i].ff.ff || c[i-1].ff.ss!=c[i].ff.ss){
        if (qw==1){
            for (int J=0; J<sd.size(); J++){
                b[sd[J]]=c[i-1].ff.ff;
            }
        }
        sd.clear();
        qw=0;
    }
   // cout<<c[i].ff.ff<<" "<<c[i].ff.ss<<" "<<c[i].ss<<" "<<sd.size()<<" "<<i<<endl;
    if (b[c[i].ss]==-1) sd.push_back(c[i].ss);
    else qw=1;
  }
  ve<int>e;
  for (int i=0; i<m; i++){
    e.pb(vx[i]-b[i]+1);
    if (b[i]==-1) e.back()=0;
  }
  return e;
}