How to solve H, M?

How to solve F?

How to solve k (King’s Palace) ? (div2)

Sadly Perl is not back here yet, although many languages are allowed.

I couldn't solve L but have ideas for it.

For a fixed query $$$v, d$$$ let $$$f_u = min_{dist(w, v) = d} dist(u, w)$$$. Then the answer is the maximum of $$$f_u$$$ over all vertices such that $$$f_u > dist(u, v)$$$.

Let's make the condition simpler. if $$$dist(u, v) > d$$$ then obviously it can't be considered as an answer. Suppose we relax the condition to $$$dist(u, v) \le d$$$. Then we may have a false candidate with $$$f_u \le dist(u, v)$$$. But they have $$$f_u \le d$$$, and these can not beat trivial solution $$$d$$$ in $$$u = v$$$, so the relaxation works.

Now we should take the maximum of $$$f_u$$$ over $$$dist(u, v) \le d$$$. Let's assume, that the query vertex $$$v$$$ is fixed but we have to answer for all $$$d$$$. Instead of fixing the vertex $$$u$$$, let's fix the deepest node $$$l$$$ where it contains both $$$u$$$ and at least one node with depth $$$d$$$. Given the depth $$$d$$$, we have to check the existence of node with depth $$$d$$$, and the deepest subtree which doesn't contain depth $$$d$$$ nodes. Say the subtree's depth is $$$x$$$, then we update the answer to $$$d + x - 2 depth_l$$$.

Then we extend this algorithm to update its value for all possible $$$d$$$. For each subtree of $$$l$$$, what only matters is the deepest node in each child's subtree of $$$l$$$. And for fixed $$$d$$$, what only matters is the two subtrees, the shallowest one with depth at least $$$d$$$ and the deepest one with depth at most $$$d - 1$$$. This means, we only have to update for adjacent subtrees in terms of deepest node. For example, if we have depth sequence $$$x_1 \le x_2 \le \ldots \le x_k$$$, then for $$$d \in [x_i + 1, x_{i+1}]$$$ we can have answer $$$d + x_i - 2 depth_l$$$. This is a classic problem. I think using sweeping is the best option.

To support arbitrary $$$v$$$, we can simply build a centroid decomposition where for each layer the above structure is stored. For each query $$$v$$$ we want to find $$$u$$$, that is in this centroid layer, but not from the subtree which contains $$$v$$$. This can be found with the above structure, but the subtree shall not contain $$$v$$$, which you can solve by maintaining two maximas or likewise.

L: We explicitly present an optimal strategy. The intuition is that the zebra should try to walk towards the lion to get information/space, and then backtrack and run away once the lion gets too close (within 2).

Let the zebra start at vertex $$$v$$$, and the lion is initially distance $$$d$$$ away. Let $$$t$$$ be the vertex furthest from $$$v$$$, and let $$$u$$$ be the furthest vertex from $$$t$$$ (so that $$$u-t$$$ forms a diameter). Our plan will be to walk around until we decide on an endpoint, and then go towards the endpoint and wait for the lion; the survival time will be the distance from the original lion location to the endpoint. This is clearly an upper bound, as the lion always makes progress every turn. Then, the precise strategy is:

Walk towards $$$t$$$ while the distance to the lion is greater than $$$2$$$ and has kept decreasing. There are 2 break conditions:

Case 1

The lion did not get closer after our last step, i.e. we walked away from the lion, and we are distance at least 3 away. Let our last step be from $$$p$$$ to $$$c$$$. Then, since we were walking towards the lion up until now, the lion must be in a different subtree of $$$p$$$ aside from $$$c$$$ and the subtree containing $$$v$$$. Because we're distance at least 3, we can use a turn to step back from $$$c$$$ to $$$p$$$.

Now, consider the furthest point from $$$p$$$; it's either $$$t$$$ or $$$u$$$. We claim this furthest point is not in the lion's subtree, so it's also the furthest point from the lion's start and thus necessarily the optimal ending point. $$$t$$$ lies in the subtree of $$$c$$$, so if $$$t$$$ is further, then we're good. If $$$u$$$ is strictly further from $$$p$$$ than $$$t$$$, then $$$u$$$ must be in the subtree of $$$p$$$ containing $$$v$$$, since we chose $$$t$$$ to be the furthest point from $$$v$$$ (otherwise, $$$u$$$ would be further from $$$v$$$).

Thus, we can always safely get to the furthest point from $$$p$$$, which is also the furthest point from the lion, which is always optimal for the lion's starting position.

Case 2

The distanced started at or decreased to at most $$$2$$$. This occurs after exactly $$$\lfloor (d-1)/2 \rfloor$$$ steps. Let the final step be from $$$p$$$ to $$$c$$$ (let $$$p$$$ be $$$\varnothing$$$ if we started at $$$d \le 2$$$). Then, note that walking in any direction which possibly contains the lion could result in dying that turn, which is always suboptimal. Thus, we should walk to and wait at the furthest vertex in a "safe" subtree (directed away from $$$c$$$), i.e. one which cannot contain the lion. There are two types of safe subtrees: (a) the $$$p$$$-subtree, which is safe because our last step took us closer to the lion, or (b) subtrees which are too shallow to contain the lion initially (all points are within $$$d-1$$$ from the start $$$v$$$). Note that the subtree of type (a) always has a path of length at least $$$\lfloor (d-1)/2 \rfloor$$$, namely the one back to $$$v$$$, and any subtree of type (b) has max depth at most $$$\lceil (d-1)/2 \rceil$$$, so subtrees of type (b) can only be useful if $$$d$$$ is even and they have max depth exactly $$$\lceil (d-1)/2 \rceil$$$.

Thus, we should look for the furthest vertex from $$$c$$$ in the direction of $$$p$$$; let this distance be $$$l$$$. If $$$c$$$ has any subtree of max depth exactly $$$\lceil (d-1)/2 \rceil$$$, let $$$l = \max(l, \lceil (d-1)/2 \rceil)$$$. Then we can survive for time $$$d + l - \lfloor (d-1)/2 \rfloor$$$.

This concludes the strategy. It turns out case 2 is always better for the lion/worse for the zebra, since they block off the furthest path, so the lion should wait along the path from $$$v$$$ to $$$t$$$ at distance $$$d$$$. (The lion can also always do at least this well by starting at this point, so this strategy is indeed optimal.)

Thus, we just need to evaluate the time that the zebra lives in case $$$2$$$. We can calculate the value described above by precomputing, for each vertex $$$c$$$, the max depth vertex in each direction/subtree, as well as the set of subtree max depths (in order to check for $$$\lceil (d-1)/2 \rceil$$$). We can do this with a simple tree DP.

#include <bits/stdc++.h>

namespace std {

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

} // namespace std

namespace ecnerwala {

using std::swap;

struct level_ancestor {
	int N;
	std::vector<int> preorder;
	std::vector<int> idx;
	std::vector<std::pair<int, int>> heavyPar; // heavy parent, distance
	level_ancestor() : N(0) {}

	level_ancestor(const std::vector<int>& par) : N(int(par.size())), preorder(N), idx(N), heavyPar(N) {
		std::vector<std::vector<int>> ch(N);
		for (int i = 0; i < N; i++) {
			if (par[i] != -1) ch[par[i]].push_back(i);
		}
		std::vector<int> sz(N);
		int nxt_idx = 0;
		for (int i = 0; i < N; i++) {
			if (par[i] == -1) {
				std::y_combinator([&](auto self, int cur) -> void {
					sz[cur] = 1;
					for (int nxt : ch[cur]) {
						self(nxt);
						sz[cur] += sz[nxt];
					}
					if (!ch[cur].empty()) {
						auto mit = max_element(ch[cur].begin(), ch[cur].end(), [&](int a, int b) { return sz[a] < sz[b]; });
						swap(*ch[cur].begin(), *mit);
					}
				})(i);
				std::y_combinator([&](auto self, int cur, int isRoot = true) -> void {
					preorder[idx[cur] = nxt_idx++] = cur;
					if (isRoot) {
						heavyPar[idx[cur]] = {par[cur] == -1 ? -1 : idx[par[cur]], 1};
					} else {
						assert(idx[par[cur]] == idx[cur]-1);
						heavyPar[idx[cur]] = heavyPar[idx[cur]-1];
						heavyPar[idx[cur]].second++;
					}
					bool chRoot = false;
					for (int nxt : ch[cur]) {
						self(nxt, chRoot);
						chRoot = true;
					}
				})(i);
			}
		}
	}

	int get_ancestor(int a, int k) const {
		assert(k >= 0);
		a = idx[a];
		while (a != -1 && k) {
			if (k >= heavyPar[a].second) {
				k -= heavyPar[a].second;
				assert(heavyPar[a].first <= a - heavyPar[a].second);
				a = heavyPar[a].first;
			} else {
				a -= k;
				k = 0;
			}
		}
		if (a == -1) return -1;
		else return preorder[a];
	}

	int lca(int a, int b) const {
		a = idx[a], b = idx[b];
		while (true) {
			if (a > b) swap(a, b);
			assert(a <= b);
			if (a > b - heavyPar[b].second) {
				return preorder[a];
			}
			b = heavyPar[b].first;
			if (b == -1) return -1;
		}
	}

	int dist(int a, int b) const {
		a = idx[a], b = idx[b];
		int res = 0;
		while (true) {
			if (a > b) swap(a, b);
			assert(a <= b);
			if (a > b - heavyPar[b].second) {
				res += b - a;
				break;
			}
			res += heavyPar[b].second;
			b = heavyPar[b].first;
			if (b == -1) return -1;
		}
		return res;
	}

	int on_path(int st, int en, int l) {
		int m = lca(st, en);
		if (l <= dist(st, m)) {
			return get_ancestor(st, l);
		} else {
			return get_ancestor(en, dist(st, en) - l);
		}
	}
};

} // namespace ecnerwala

int main() {
	using namespace std;
	ios_base::sync_with_stdio(false), cin.tie(nullptr);

	int N, Q; cin >> N >> Q;
	std::vector<std::vector<int>> adj(N);
	for (int e = 0; e < N-1; e++) {
		int u, v; cin >> u >> v; u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	std::vector<int> par(N);
	std::vector<std::pair<int, int>> furthest_down(N);
	std::y_combinator([&](auto self, int cur, int prv) -> void {
		par[cur] = prv;
		furthest_down[cur] = {0, cur};
		for (int nxt : adj[cur]) {
			if (nxt == prv) continue;
			self(nxt, cur);
			auto v = furthest_down[nxt];
			v.first++;
			furthest_down[cur] = max(furthest_down[cur], v);
		}
	})(0, -1);
	std::vector<std::pair<int, int>> furthest_up(N);
	std::vector<std::pair<int, int>> furthest(N);
	std::vector<std::set<int>> ch_dist(N);
	std::y_combinator([&](auto self, int cur, int prv) -> void {
		std::pair<int, int> furthest1{0, cur};
		std::pair<int, int> furthest2{-1, -1};
		for (int nxt : adj[cur]) {
			auto v = nxt == prv ? furthest_up[cur] : furthest_down[nxt];
			v.first++;
			ch_dist[cur].insert(v.first);
			if (v > furthest1) {
				furthest2 = furthest1;
				furthest1 = v;
			} else if (v > furthest2) {
				furthest2 = v;
			}
		}
		furthest[cur] = furthest1;
		for (int nxt : adj[cur]) {
			if (nxt == prv) continue;
			auto v = furthest_down[nxt];
			v.first++;
			if (v == furthest1) {
				furthest_up[nxt] = furthest2;
			} else {
				furthest_up[nxt] = furthest1;
			}
			self(nxt, cur);
		}
	})(0, -1);
	/*
	cerr << "global" << '\n';
	for (int i = 0; i < N; i++) {
		cerr << i << ' ' << furthest[i].first << ' ' << furthest[i].second << '\n';
	}
	cerr << "down" << '\n';
	for (int i = 1; i < N; i++) {
		cerr << i << ' ' << furthest_down[i].first << ' ' << furthest_down[i].second << '\n';
	}
	cerr << "up" << '\n';
	for (int i = 1; i < N; i++) {
		cerr << i << ' ' << furthest_up[i].first << ' ' << furthest_up[i].second << '\n';
	}
	*/

	ecnerwala::level_ancestor anc(par);

	auto solve_query = [&](int v, int d) {
		//cerr << "solve_query " << v << ' ' << d << '\n';
		assert(d > 0);
		assert(furthest[v].first >= d);
		int turn_pt = anc.on_path(v, furthest[v].second, (d-1)/2);
		int ans = d;
		//cerr << "turn_pt " << turn_pt << '\n';
		if (d > 2) {
			int anc_pt = anc.on_path(v, furthest[v].second, (d-1)/2 - 1);
			//cerr << "anc_pt " << anc_pt << '\n';
			int l;
			if (anc_pt == par[turn_pt]) {
				l = furthest_up[turn_pt].first;
			} else if (par[anc_pt] == turn_pt) {
				l = furthest_down[anc_pt].first;
			} else assert(false);
			assert(l >= ((d-1)/2 - 1));
			//cerr << "len " << l << '\n';
			ans = std::max(ans, d + (l - ((d-1)/2 - 1)));;
		}
		if (d % 2 == 0 && ch_dist[turn_pt].count(d/2)) {
			ans = std::max(ans, d+1);
		}
		return ans;
	};

	for (int q = 0; q < Q; q++) {
		int v, d; cin >> v >> d; v--;
		cout << solve_query(v, d) << '\n';
	}

	return 0;
}

How to solve J?