1790F - Timofey and Black-White Tree - CodeForces Solution

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

#define int long long
typedef pair<int, int> pii;
typedef long long ll;


const int N = 2e5 + 1, LOG = 20;

vector<int> arr[N];

int used[N], sz[N], dist[LOG][N], levels[N], par[N];

void dfs(int v, int par) {
	sz[v] = 1;
	for (int u : arr[v])
		if (!used[u] && u != par) {
			dfs(u, v);
			sz[v] += sz[u];
		}
}

int clevel, ans[N];

void dfs1(int v, int par) {
	for (int u : arr[v]) {
		if (!used[u] && u != par) {
			dist[clevel][u] = dist[clevel][v] + 1;
			dfs1(u, v);
		}
	}
}

void cd(int v, int cpar) {
	dfs(v, -1);
	int csz = sz[v] / 2, prev = -1;
	bool flag;
	do {
		flag = false;
		for (int u : arr[v])
			if (u != prev && !used[u] && sz[u] > csz) {
				prev = v;
				v = u;
				flag = true;
				break;
			}
	} while (flag);
	used[v] = 1;
	par[v] = cpar;
	levels[v] = levels[cpar] + 1;
	clevel = levels[v];
	dfs1(v, -1);
	for (int u : arr[v])
		if (!used[u])
			cd(u, v);
}

int query(int v) {
	int cans = ans[v];
	int stv = v;
	while (levels[v] != 1) {
		v = par[v];
		cans = min(cans, ans[v] + dist[levels[v]][stv]);
	}
	return cans;
}

void change(int v) {
	ans[v] = 0;
	int stv = v;
	while (levels[v] != 1) {
		v = par[v];
		ans[v] = min(ans[v], dist[levels[v]][stv]);
	}
}

void solve() {
	int n, f, s, start;
	cin >> n >> start;
	start--;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < LOG; j++)
			dist[j][i] = 0;
		used[i] = 0;
		arr[i].clear();
		levels[i] = -1;
		ans[i] = 1e8;
	}
	vector<int> queries(n);
	for (int i = 0; i < n - 1; i++) {
		cin >> queries[i];
	}
	for (int i = 0; i < n - 1; i++) {
		cin >> f >> s;
		f--;
		s--;
		arr[f].push_back(s);
		arr[s].push_back(f);
	}
	cd(0, -1);
	change(start);
	int cans = 1e8;
	for (int i = 0; i < n - 1; i++) {
		cans = min(cans, query(queries[i] - 1));
		change(queries[i] - 1);
		cout << cans << " ";
	}
	cout << "\n";
}


signed main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output1.txt", "w", stdout);
	cin.tie(0)->sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) 
		solve();
}