#include "infection.h"
#include <vector>
#include <utility>
#include<bits/stdc++.h>
using namespace std;

const long long MAXN = 150001;

vector<long long> haha[MAXN];
long long bruh[MAXN][19];
vector<long long> dep(MAXN);

void dfs(long long a, long long t, long long d) {
    dep[a] = d;
    bruh[a][0] = t;
    for(int v: haha[a]) {
        if(v != t) {
            dfs(v,a,d+1);
        }
    }
}

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> z
) {
    long long n = r.size()+1;
    long long m = s.size();
    for(long long i = 0; i < n-1; i++) {
        haha[r[i].first].push_back(r[i].second);
        haha[r[i].second].push_back(r[i].first);
    }
    dfs(0,-1,0);
    for(int i = 1; i < 19; i++) {
        for(int j = 0; j < n; j++) {
            if(bruh[j][i-1] == -1) {
                bruh[j][i] = -1;
            }
            else {
                bruh[j][i] = bruh[bruh[j][i-1]][i-1];
            }
        }
    }
    vector<int> ans(m);
    for(int i = 0; i < m; i++) {
        if(!z[i]) {
            continue;
        }
        int a = s[i],b = t[i];
        if(dep[a] < dep[b]) {
            swap(a,b);
        }
        int y = dep[a]-dep[b];
        int sb = 0;
        for(int j = 0; j < 19; j++) {
            if((1 << j)&y) {
                a = bruh[a][j];
                sb+=(1 << j);
            }
        }
        if(a != b) {
            for(int j = 18; j >= 0; j--) {
                if(bruh[a][j] != bruh[b][j]) {
                    a = bruh[a][j];
                    b = bruh[b][j];
                    sb+=(1 << j)*2;
                }
            }
            sb+=2;
        }
        ans[i] = sb;
    }
    return ans;
}
