#include <bits/stdc++.h>
using namespace std;
using ll = long long;
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()


vvl g;
vvl pr;
vll dep;
void dfs(ll cur){
    for(ll i:g[cur]){
        if(i!=pr[0][cur]){
            pr[0][i]=cur;
            dep[i]=dep[cur]+1;
            dfs(i);
        }
    }
}
ll find_pr(ll a, ll i){
    for(ll f = 19; f>= 0; --f){
        if(i&(1<<f)){
            a=pr[f][a];
        }
    }
    return a;
}
ll lca(ll a, ll b){
    if(dep[b]>dep[a])swap(a,b);
    a = find_pr(a,dep[a]-dep[b]);
    if(a==b)return a;
    for(ll f = 19; f >= 0; --f){
        if(pr[f][a]!=pr[f][b]){
            a=pr[f][a];
            b=pr[f][b];
        }
    }
    return pr[0][a];
}

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);
    }
    pr = vvl(20, vll(n));
    dep=vll(n);
    dfs(0);
    for(ll f = 1; f < 20; ++f){
        for(ll i = 0; i < n; ++i){
            pr[f][i]=pr[f-1][pr[f-1][i]];
        }
    }
    for(ll i = 0; i < n; ++i){
        if(inf[i]){
            ans[i] = dep[s[i]]+dep[t[i]]-2*dep[lca(s[i],t[i])];
        }
    }
    return ans;
}