Balkan OI 2017 - City Attractions

Introduction

Let the node that Gigel goes to from node $i$ be $t_i$. Since the graph made from the directed edges $i \rightarrow t_i$ is a functional graph, we can use binary jumping or any other efficient method to find the final node.

Now we only need to find all $t_i$ and we are done! However, this isn't as straightforward as it sounds...

A simpler problem

Let's consider a simpler problem: suppose we root the tree at node $1$ and Gigel can only move down the tree (don't worry about the leaves). In this problem, we can find all $t_i$ (and $a[t_i] - dist(i, t_i)$) using a simple tree DP:

Let $dp[i]$ be the node in the subtree of $i$ (excluding $i$ itself) such that $a[dp[i]] - dist(i, dp[i])$ is maximized. Additionally, we store this value in the DP array. We can find $dp[i]$ by taking the best of $c$ and $dp[c]$ over all children $c$ of $i$.

This algorithm runs in $\mathcal{O}(N)$ time.

Finding all $t_i$

Obviously, the solution to the simpler problem doesn't solve the general problem: we might need to move up into a node's parent!

To address this issue, we can first do a DFS to find $dp$ as defined above, and then do a second DFS to allow moving outside our subtree. See the solving for all roots module if you're unfamiliar with this technique. Essentially, we find the best destination from $i$ if we move up into $i$'s parent and then compare that with $dp[i]$.

After doing this, $dp[i]$ is simply $t_i$ as desired.

Finding the final destination

There are two ways we can go about finding Gigel's final location.

1. We can implement binary jumping on our array containing the next location
2. We try to reach a cycle, and then take our remaining jumps modulo the cycle size

The first method is a tad easier to implement, but introduces a log factor.

Implementation 1

Time Complexity: $O(N \log{K})$

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
	int n;
	ll k;
	cin >> n >> k;

Implementation 2

Time Complexity: $O(N)$

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
	int n;
	ll k;
	cin >> n >> k;