Navigation

Esencialmente queremos enraizar el árbol en $T$ y siempre movernos al padre del nodo actual hasta terminar en $T$ .

Pista 1

Para resolver la última subtarea, hay que aprovechar al máximo tanto los números de las islas como los números escritos en las banderas.

Pista 2

Dados dos vértices adyacentes $u$ y $v$ , deberíamos poder decir cuál de $u$ y $v$ está más cerca de $T$ a partir de los pares $(u,F[u])$ y $(v,F[v])$ .

Pista 3

Escribimos en las banderas de modo que $F[u]\oplus F[v]=0$ implique que $\min(u,v)$ está más cerca de $T$ (mientras que $F[u]\oplus F[v]=1$ implica que $\max(u,v)$ está más cerca de $T$ ).

Solución

Anna.cpp


#include "Annalib.h"
#include <bits/stdc++.h>
using namespace std;
 
static vector<int> graph[100001];
static int val[100001];
 
static void dfs(int node, int parent) {
	val[node] = val[parent] ^ (parent < node);
	Flag(node, val[node]);
	for (int i : graph[node])
		if (i != parent) dfs(i, node);
}
 
void Anna(int K, int N, int T, int A[], int B[]) {
	for (int i = 0; i < N - 1; i++) {
		graph[A[i]].push_back(B[i]);
		graph[B[i]].push_back(A[i]);
	}
	dfs(T, 0);
}

Bruno.cpp


#include "Brunolib.h"
#include <bits/stdc++.h>
using namespace std;
 
void Bruno(int K, int S, int F, int L, int P[], int Q[]) {
	for (int i = 0; i < L; i++) {
		if (!((P[i] < S) ^ F ^ Q[i])) {
			Answer(P[i]);
			return;
		}
	}
	Answer(S);
}