#include "infection.h"
#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

typedef long long llong;

const int MAXN = 2e5 + 10;
const int MAXLOG = 19;
const llong INF = 1e18 + 10;

int n, m;
vector < int > adj[MAXN];
vector < vector < pair < int, llong > > > paths;
vector < pair < int, llong > > curpath;
int ptr[MAXN];
llong inf[MAXN];
set < int > which[MAXN];

void dfs(int u, int p, llong tim, int to)
{
    curpath.push_back({u, tim});

    if(u == to)
    {
        paths.push_back(curpath);
        return;
    }

    for(int& v : adj[u])
    {
        if(v == p)
            continue;

        dfs(v, u, tim + 1, to);
    }

    curpath.pop_back();
}

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();

    for(int i = 0; i < n - 1; i++)
    {
        adj[R[i].first].push_back(R[i].second);
        adj[R[i].second].push_back(R[i].first);
    }

    for(int i = 0; i < m; i++)
    {
        curpath.clear();
        dfs(S[i], S[i], D[i], T[i]);
    }

    vector < llong > ds;

    for(int i = 0; i < m; i++)
    {   
        int sz = paths[i].size();

        for(int j = 0; j < sz; j++)
        {
            ds.push_back(paths[i][j].second);
        }
    }

    sort(ds.begin(), ds.end());
    ds.erase(unique(ds.begin(), ds.end()), ds.end());

    for(int i = 0; i < m; i++)
    {
        inf[i] = (I[i] ? D[i] : INF);
    }

    for(llong& d : ds)
    {
        for(int i = 0; i < m; i++)
        {
            if(ptr[i] < paths[i].size() && paths[i][ptr[i]].second == d)
            {
                if(ptr[i] != 0)
                {
                    which[paths[i][ptr[i] - 1].first].erase(i);
                }

                which[paths[i][ptr[i]].first].insert(i);
                ptr[i]++;
            }

            if(ptr[i] == paths[i].size() && paths[i].back().second > d)
            {
                which[paths[i].back().first].erase(i);
            }
        }

        for(int i = 0; i < n; i++)
        {
            bool has = false;

            for(int g : which[i])
            {
                if(inf[g] <= d)
                {
                    has = true;
                    break;
                }
            }

            if(has)
            {
                for(int g : which[i])
                {
                    inf[g] = min(inf[g], d);
                }
            }
        }
    }

    vector < int > ans(m);

    for(int i = 0; i < m; i++)
    {
        if(inf[i] == INF)
            ans[i] = 0;
        else
            ans[i] = paths[i].back().second - inf[i] + 1;
    }

    return ans;
}
/**

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 0
4 5 7 0
8 7 8 0
10 0 1 0
*/