#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <iterator>
#include <cassert>
#include <queue>
#include "infection.h"
using namespace std;

#define dbg(x) cerr << #x << ' '; print(x); cerr << endl;
void print(int x) { cerr << x; }
void print(long long x) { cerr << x; }
void print(char x) { cerr << x; }
void print(string x) { cerr << x; }
void print(double x) { cerr << x; }
template <class T> void print(vector <T> x);
template <class T> void print(vector <T> x) { cerr << "[ "; for (T i : x) { print(i); cerr << ' '; } cerr << ']'; }
template <class T> void print(set <T> x) { cerr << "[ "; for (T i : x) { print(i); cerr << ' '; } cerr << ']'; }
template <class T> void print(multiset <T> x) { cerr << "[ "; for (T i : x) { print(i); cerr << ' '; } cerr << ']'; }
template <class T, class V> void print(pair <T, V> x) { cerr << "{"; print(x.first); cerr << ' '; print(x.second); cerr << "}"; }

#define ll long long
#define OK cerr << "OK\n"
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define PII pair <int, int>
#define MP make_pair
#define inf 1e9 + 5
#define inf64 1e18 + 5;
#define pb push_back

const int N = 5005;
int n, m, p[N];
vector <int> G[N], answ, path[N], timer, er;
map <ll, bool> mp;
set <ll> days;
set <int> active;
vector <bool> infected;

bool dfs(int node, int parent, int st, int en, int indx) {
	p[node] = parent;
	if (node == en) {
		while (node != st) {
			path[indx].pb(node);
			node = p[node];
		}
		path[indx].pb(st);
		reverse(all(path[indx]));
		return 1;
	}
	for (int u : G[node]) {
		if (u == parent) continue;
		if (dfs(u, node, st, en, indx)) return 1;
	}
	return 0;
}

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() + 1;
	m = D.size();
	for (int i = 0; i < n - 1; i++) {
		G[R[i].first].pb(R[i].second);
		G[R[i].second].pb(R[i].first);
	}
	for (int i = 0; i < m; i++) {
		dfs(S[i], -1, S[i], T[i], i);
	}
	answ.assign(m, 0);

	/*OK;
	for (int i = 0; i < m; i++) {
		dbg(path[i]);
	}*/

	for (int i = 0; i < m; i++) {
		days.insert(D[i]);
		for (ll j = D[i]; j < D[i] + path[i].size(); j++) days.insert(j);
		mp[D[i]] = 1;
	}
	timer.assign(m, -1);
	infected.assign(n, 0);
	for (ll d : days) {
		if (mp[d]) {
			for (int i = 0; i < m; i++) {
				if (D[i] == d) {
					timer[i] = 0;
					active.insert(i);
				}
			}
		}
		for (int i : active) {
			infected[path[i][timer[i]]] = 0;
		}
		for (int i : active) {
			if (I[i]) infected[path[i][timer[i]]] = 1;
		}
		er.clear();
		for (int i : active) {
			if (infected[path[i][timer[i]]]) I[i] = 1;
			answ[i] += I[i];
			timer[i]++;
			if (timer[i] == path[i].size()) er.pb(i);
		}
		for (int i : er) active.erase(i);
	}
	return answ;
}
