#include <bits/stdc++.h>
#include "infection.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

vector<int> nodes[150005];
vector<signed> sol;
int p[150005];
int up[20][150005];
int h[150005];

void dfs(int node, int parent)
{
     p[node]=parent;
     for (auto x : nodes[node])
     {
          if (x!=parent)
          {
              h[x]=h[node]+1;
              dfs(x,node);
          }
     }
}

int lca(int u, int v)
{
    int i,k;
    if (h[u]<h[v])
        swap(u,v);
    k=h[u]-h[v];
    for (i=0;i<=17;i++)
    {
         if (k&(1<<i))
             u=up[i][u];
    }
    if (u==v)
        return u;
    for (i=17;i>=0;i--)
    {
         if (up[i][u]!=up[i][v])
         {
             u=up[i][u];
             v=up[i][v];
         }
    }
    return up[0][u];
}

int dist(int u, int v)
{
    int c;
    c=lca(u,v);
    return (h[u]-h[c]+h[v]-h[c]+1);///probabil aici e greseala
}

std::vector<signed> solve(
    std::vector<std::pair<signed, signed>> R,
    std::vector<long long> D,
    std::vector<signed> S,
    std::vector<signed> T,
    std::vector<bool> I
)
{
    int n,m,i,j;
    for (auto x : R)
    {
         x.first++;
         x.second++;
         nodes[x.first].push_back(x.second);
         nodes[x.second].push_back(x.first);
    }

    h[1]=0;
    dfs(1,1);
    n=R.size()+1;
    m=I.size();
    for (i=0;i<m;i++)
    {
         S[i]++;
         T[i]++;
    }
    for (i=1;i<=n;i++)
    {
         up[0][i]=p[i];
         for (j=1;j<=17;j++)
         {
              up[j][i]=up[j-1][up[j-1][i]];
         }
    }
    for (i=0;i<m;i++)
    {
         if (I[i]==0)
         {
             sol.push_back(0);
         }
         else
         {
             sol.push_back(dist(S[i],T[i]));
         }
    }
    return sol;
}
/*
9 5
0 1
1 2
2 3
3 4
4 5
3 6
6 7
6 8
1 0 5 1
3 5 7 1
4 5 7 1
8 7 8 1
10 0 1 1
*/


