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

const int MAXN = 15e4;
const int LOG = 20;

int n , up[LOG + 1][MAXN + 1] , par[MAXN + 1] , niv[MAXN + 1] , ans , cnt;
vector< int >edges[MAXN + 1];
struct elem {
    int nod , t;
    bool operator <( const elem &a ) const {
        return t < a.t;
    }
};
map< elem , int >f;
void init() {
    int i , j;
    for( i = 1 ; i <= n ; i++ )
        up[0][i] = par[i];
    for( j = 1 ; j < LOG ; j++ )
        for( i = 1 ; i <= n ; i++ )
            up[j][i] = up[j - 1][up[j - 1][i]];
}
void dfs( int nod , int p ) {
    par[nod] = p;
    niv[nod] = niv[p] + 1;
    for( auto x : edges[nod] )
        if( x != p )
            dfs( x , nod );
}
int kth( int nod , int k ) {
    int i;
    //cout << nod - 1 << ' ';
    for( i = 0 ; ( 1 << i ) <= k ; i++ )
        if( ( 1 << i ) & k )
            nod = up[i][nod];
    //cout << nod - 1 << '\n';
    return nod;
}
void updnode( int st , int dr , int t , int val ) {
    //cout << st << ' ' << dr << ' ' << t << ' ' << val << '\n';
    while( st != dr ) {
        //cout << t << ' ' << st << '\n';
        f[{ st , t }] = 1;
        st = par[st];
        t += val;
    }
    //cout << t << ' ' << st << '\n';
    f[{ st , t }] = 1;
}
void calcnode( int st , int dr , int t , int val ) {
    int cop;
    while( st != dr ) {
        //cout << t << ' ' << st << '\n';
        ans += f[{ st , t }];
        st = par[st];
        t += val;
    }
    if( val == 1 )
        ans += f[{ st , t }];
    //cout << t << ' ' << st << '\n';
}
void lca( int a , int b , int t , int what ) {
    int nod , i , cop1 , cop2;
    cop1 = a;
    cop2 = b;
    if( niv[a] < niv[b] )
        swap( a , b );
    a = kth( a , niv[a] - niv[b] );
    for( i = LOG - 1 ; i >= 0 ; i-- )
        if( up[i][a] != up[i][b] ) {
            a = up[i][a];
            b = up[i][b];
        }
    if( a != b ) {
        a = up[0][a];
        b = up[0][b];
    }
    nod = a;
    a = cop1;
    b = cop2;
    //cout << a << ' ' << b << ' ' << nod << '\n';
    if( what == 0 ) {
        updnode( a , nod , t , 1 );
        t = t + niv[a] - niv[nod] + niv[b] - niv[nod];
        updnode( b , nod , t , -1 );
    } else {
        //cout << cnt << '\n';
        calcnode( a , nod , t , 1 );
        t = t + niv[a] - niv[nod] + niv[b] - niv[nod];
        calcnode( b , nod , t , -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
) {
    int i , j ,  m = D.size();
    n = R.size() + 1;
    vector< int >rasp;
    for( auto [ a , b ] : R ) {
        a++;
        b++;
        edges[a].push_back( b );
        edges[b].push_back( a );
    }
    dfs( 1 , 0 );
    init();
    for( i = 0 ; i < m ; i++ ) {
        S[i]++;
        T[i]++;
    }
    cnt = 1;
    for( i = 0 ; i < m ; i++ ) {
        if( I[i] == 0 )
            continue;
        lca( S[i] , T[i] , D[i] , 0 );
    }
    for( i = 0 ; i < m ; i++ ) {
        ans = 0;
        lca( S[i] , T[i] , D[i] , 1 );
        rasp.push_back( ans );
        cnt++;
    }
    return rasp;
}
