#include "infection.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef vector<ll> vl;

const int MAX_N=150000+5;
vi G[MAX_N];
int tin[MAX_N];
int tout[MAX_N];
const int MAX_LOG=18;
int anc[MAX_N][MAX_LOG];
int dep[MAX_N];
int t=0;

void dfs_init(int u, int p){
    tin[u]=t++;
    anc[u][0]=p;
    for(int i=1; i<MAX_LOG; i++) anc[u][i]=anc[anc[u][i-1]][i-1];
    for(int v : G[u]){
        if(v==p) continue;
        dep[v]=dep[u]+1;
        dfs_init(v, u);
    }
    tout[u]=t++;
}

bool is_anc(int u, int v){
    return (tin[u]<=tin[v] && tout[u]>=tout[v]);
}

int lca(int u, int v){
    if(is_anc(u, v)) return u;
    for(int i=MAX_LOG-1; i>=0; i--){
        if(!is_anc(anc[v][i], u)) v=anc[v][i];
    }
    return anc[v][0];
}
int dist(int u, int v){
    return dep[u]+dep[v]-2*dep[lca(u, v)];
}

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> I
) {
    int N=R.size()+1;
    for(int i=0; i<N-1; i++){
        G[R[i].first].push_back(R[i].second);
        G[R[i].second].push_back(R[i].first);
    }
    dep[0]=0;
    dfs_init(0, 0);
    int M=S.size();
    // if(M<=5000){
    //     //find out all intersections
    //     vector<pair<ll, pii>> meet;
    //     for(int i=0; i<M; i++){
    //         for(int j=i+1; j<M; j++){
    //             //check if and when they cut each other
    //             ll a=dist(S[i], S[j]), b=dist(S[i], T[j]), c=dist(T[i], S[j]), d=dist(T[i], T[j]), e=dist(S[i], T[i]), f=dist(S[j], T[j]);
    //             if(a+b-f+c+d-f>2*e) continue;
    //             //that meant they didn't cut each other.
    //             //first time they meet is a+b-f
    //             if((a+b-f)/2+D[i]==(a-(a+b-f)/2)+D[j]){
    //                 //they meet here
    //                 meet.push_back({(a+b-f)/2+D[i], {i, j}});
    //                 continue;
    //             }
    //             //there is another case
    //             //they go in opposite directions
    //             if(e+d-b>c+d-f){
    //                 //this means they are in opposite directions. 
    //                 //when do they meet?
    //                 if((D[i]+D[j]-a)%2!=0) continue;
    //                 int dd=(D[i]+D[j]+a)/2;
    //                 if((D[j]-D[i]+a)/2>=(b+e-d)/2 && (D[i]-D[j]+a)/2>=(c+f-d)/2){
    //                     //they meet!
    //                     meet.push_back({dd, {i, j}});
    //                 }
    //             }
    //         }
    //     }
    //     sort(meet.begin(), meet.end());
    //     vl inf_day(M, 1e13);
    //     for(int i=0; i<M; i++) if(I[i]) inf_day[i]=D[i];
    //     for(auto[a, b] : meet){
    //         int i=b.first, j=b.second;
    //         if(inf_day[i]!=1e13) inf_day[j]=min(inf_day[j], a);
    //         if(inf_day[j]!=1e13) inf_day[i]=min(inf_day[i], a);
    //     }
    //     vi ans(M, 0);
    //     for(int i=0; i<M; i++){
    //         ans[i]=max((ll)0, (ll)(dist(S[i], T[i])+1-inf_day[i]+D[i]));
    //     }
    //     return ans;
    // }
    vi ans(M, 0);
    for(int i=0; i<M; i++){
        if(I[i]) ans[i]=dist(S[i], T[i])+1;
    }
    return ans;
}