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

const int MN = 5e3 + 3;

vector<int> v[MN];

int a[MN][MN],p[MN],n,m;

bool f[MN],kr[MN];

void dfs(int u){

    for(auto i: v[u]){

        if(i!=p[u]){
            p[i]=u;
            dfs(i);
            a[u][i]=i;
            for(int j=0;j<n;j++){
                if(j==i && j==u)continue;
                if(a[i][j]!=-1)a[u][j]=i;
            }
        }

    }

}

vector<int> solve(
    vector<std::pair<int, int>> R,
    vector<long long> D,
    vector<int> S,
    vector<int> T,
    vector<bool> I
) {



    n=R.size();
    m=D.size();

    vector<int> ans(m,0);

    for(int i=0;i<n-1;i++){

        v[R[i].first].pb(R[i].second);
        v[R[i].second].pb(R[i].first);

    }

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            a[i][j]=-1;
        }
    }

    p[0]=-1;
    dfs(0);

    int br=0;

    for(int i=0;;i++){

        for(int j=0;j<n;j++){
            f[j]=0;
        }
        for(int j=0;j<m;j++){
            if(kr[j]==1)continue;
            if(I[j]==1){
                f[S[j]]=1;
            }
        }
        for(int j=0;j<m;j++){
            if(kr[j]==1)continue;
            if(f[S[j]]==1){
                I[j]=1;
            }
            if(I[j]==1)ans[j]++;
        }

        for(int j=0;j<m;j++){

            if(kr[j]==1)continue;
            if(S[j]==T[j]){
                kr[j]=1;
                br++;
                continue;
            }

            if(a[S[j]][T[j]]==-1)S[j]=p[S[j]];
            else{
                S[j]=a[S[j]][T[j]];
            }


        }

        if(br==m)break;

    }




    return ans;






}
