#include "infection.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=150000;
vector<int>adj[MAXN+1];
int tin[MAXN+1],tout[MAXN+1];
int up[MAXN+1];

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

vector<int>get_path(int s,int t) {
    vector<int>res;
    while(!is_anc(s,t)) {
        res.push_back(s);
        s=up[s];
    }
    res.push_back(s);
    vector<int>r;
    while(t!=s) {
        r.push_back(t);
        t=up[t];
    }
    reverse(r.begin(),r.end());
    for(auto it:r) {
        res.push_back(it);
    }
    return res;
}

int timer=0;
int dep[MAXN+1];

void dfs(int u,int pr) {
    up[u]=pr;
    tin[u]=++timer;
    for(auto v:adj[u]) {
        if(v!=pr) {
            dep[v]=1+dep[u];
            dfs(v,u);
        }
    }
    tout[u]=timer;
}
int city[MAXN+1];
int fr[MAXN+1];
int jump[MAXN+1][21];

int lca_path(int u,int v) {
    int len=0;
    if(dep[u]>dep[v]){
        swap(u,v);
    }
    int diff=dep[v]-dep[u];
    for(int i=20;i>=0;i--){
        if(diff&(1<<i)){
            len+=(1<<i);
            v=jump[v][i];
        }
    }
    if(u==v){
        return len;
    }
    for(int i=20;i>=0;i--){
        if(up[u][i]!=up[v][i]){
            u=jump[u][i];
            v=jump[v][i];
            len+=(1<<(i+1));
        }
    }
    u=up[u][0];
    v=up[v][0];
    len+=2;
    return len;
}

int n,m;

void binlift() {
    for(int i=1; i<=n; i++) {
        jump[i][0]=up[i];
    }
    for(int j=1; j<=20; j++) {
        for(int i=1; i<=n; i++) {
            jump[i][j]=jump[jump[i][j-1]][j-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> I) {
    n=R.size()+1,m=D.size();
    //vector<int>path[m+1];
    vector<int>days(m,0);
    int mx=0;
    for(auto it:R) {
        int u=it.first,v=it.second;
        adj[u+1].push_back(v+1);
        adj[v+1].push_back(u+1);
    }
    dfs(1,0);
    /*for(int i=1; i<=m; i++) {
        path[i]=get_path(S[i-1]+1,T[i-1]+1);
        mx=max(mx,(int)path[i].size());
    }
    for(int i=0;i<mx;i++){
        for(int person=1;person<=m;person++){
            if(i<path[person].size()){
               bool inf=I[person-1];
               fr[city[person]]-=inf;
               city[person]=path[person][i];
               fr[city[person]]+=inf;
            }
        }
        for(int person=1;person<=m;person++){
            if(i<path[person].size()){
                if(fr[city[person]]&&!I[person-1]){
                    I[person-1]=true;
                    fr[city[person]]++;
                }
                if(I[person-1]){
                    days[person-1]++;
                }
            }
        }
    }*/
    binlift();
    for(int i=0; i<m; i++) {
        if(I[i]) {
            days[i]=lca_path(S[i]+1,T[i]+1);
        }
    }
    return days;
}

/*
signed main() {
    int n, m;

    std::cin >> n;
    std::cin >> m;

    std::vector<std::pair<int, int>> edges = {};
    std::vector<long long> day;
    std::vector<int> start;
    std::vector<int> target;
    std::vector<bool> infected;

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        std::cin >> u >> v;
        edges.emplace_back(u, v);
    }

    for (int i = 0; i < m; i++) {
        long long _d, _s, _t, _i;
        std::cin >> _d >> _s >> _t >> _i;
        day.push_back(_d);
        start.push_back(_s);
        target.push_back(_t);
        infected.push_back(_i);
    }

    const auto ans = solve(edges, day, start, target, infected);
    for (const auto it : ans) {
        std::cout << it << std::endl;
    }

    return 0;
}*/

