We need to simplify the input. Let's define a graph on $$$2n$$$ vertices $$$V_1, V_2, ..., V_n, W_1, W_2, ..., W_n$$$. $$$V_i$$$ and $$$W_i$$$ represent the state of being in vertex $$$i$$$, but $$$W_i$$$ imposes the additional restriction that you just came from the largest edge.

For a vertex $$$i$$$ let $$$ij$$$ be the largest edge connected with $$$i$$$, and let $$$ik$$$ to be the second largest, or $$$j$$$ if it's the only neighbor. We will add the following edges:

• $$$V_i \rightarrow V_j$$$ or $$$W_j$$$ depending on whether $$$ij$$$ is the biggest edge for $$$j$$$ or not.

• $$$W_i \rightarrow V_k$$$ or $$$W_k$$$ depending on whether $$$ik$$$ is the biggest edge for $$$k$$$ or not.

The task now simply to count the number of vertices among $$$V_1, V_2, ..., V_n$$$ that end up at $$$V_p$$$ or $$$W_p$$$ after taking $$$k$$$ steps in this state graph. Now we have a bruteforce $$$\operatorname{O}(nk)$$$ solution per query. You can also achieve this complexity by simple brute force.

It's possible to solve this task in $$$\operatorname{O}(n \log k)$$$ per query by going through each vertex and finding where it ends up in $$$k$$$ steps using binary lifting. This gets the first 2 subtasks and 69 points.

Full points may or may not be easier than getting just 69.

We need to understand the structure of the graph we have built. Each component looks a bunch of rooted trees, where some of the roots have been connected in a cycle. This means that if $$$t$$$ is in a cycle of length $$$3$$$, and min number of steps for some vertex $$$s$$$ to reach $$$t$$$ is $$$4$$$ for example, then it will visit $$$t$$$ after $$$7, 10, 13, ..., 67, ...$$$ steps as well.

Let's focus on $$$V_p$$$ for now, as all these checks can be done for $$$W_p$$$ just as well. We will reverse all the edges and calculate the distance from $$$V_p$$$ to all other vertices. Let these distances be called $$$d_i$$$. Also let $$$c$$$ be the length of the cycle $$$V_p$$$ is in or $$$93858158317519$$$ if it's not in a cycle. Then all we have to do to check if $$$V_i$$$ reaches $$$V_p$$$ in $$$k$$$ steps is:

• $$$d_{V_i} \ge k$$$
• $$$d_{V_i} - k$$$ is a multiple of $$$c$$$

So we can answer a query in $$$\operatorname{O}(n)$$$ per query.

Looking at the manhattan distance is hard and annoying. An easier and more straightforward calculation would be to find the number of diagonals and antidiagonals that seperate the two cells, and check that the bigger of them is $$$k$$$. The name of the game is to collapse down the diagonals and antidiagonals into a single cell and do some calculations on them.

For each diagonal and antidiagonal, check if it contains exactly 1 black cell. We can do this by $$$\operatorname{OR}$$$-ing and $$$\operatorname{XOR}$$$-ing the whole diagonal/antidiagonal and $$$\operatorname{AND}$$$-ing them together. This takes roughly $$$2(n + m)$$$ instructions and their total length is $$$2nm$$$.

Given an array of $$$L$$$ boolean variables $$$a_1, a_2, ..., a_L$$$, two of which are True. Determine if they are at a distance of $$$k$$$. This will be useful for determining if the black cells are exactly $$$k$$$ diagonals or antidiagonals away from each other.

This can be done by going through $$$1, 2, ..., n-k$$$, computing $$$a_i \operatorname{AND} a_{i+k}$$$, and $$$\operatorname{OR}$$$-ing them together. This is roughly $$$2(N + M)$$$ with total length $$$4(n + m)$$$.

Given an array of $$$L$$$ boolean variables $$$a_1, a_2, ..., a_L$$$, two of which are True. Determine if they are at a distance of $$$k$$$ or less. It will actually be easier to check if they are further than $$$k$$$ apart.

We will calculate "suffix $$$\operatorname{OR}$$$." Let this array be called $$$s_1, s_2, ..., s_L$$$. Now it's simple, we just need to take $$$\operatorname{AND}$$$ of $$$a_i$$$ and $$$s_{i+k+1}$$$ and take $$$\operatorname{OR}$$$ of those. This needs about $$$4(n + m)$$$ instructions and total length $$$8(n + m)$$$.

Let $$$a$$$ be the diagonal distance and $$$b$$$ be the antidiagonal distance. Using the algorithms from parts 2 and 3, we have found whether:

• $$$a = k$$$

• $$$a ≤ k$$$

• $$$b = k$$$

• $$$b ≤ k$$$

So we just need take $$$\operatorname{AND}$$$ of first and fourth, $$$\operatorname{AND}$$$ of second and third, and $$$\operatorname{OR}$$$ those together.

This is one of my favorite IOI tasks. I love tasks like this and 2021's Registers that give you an esoteric set of instructions that have you compute something. Comparing these tasks with Tropical Garden is like night and day. I wish tasks like this were more common, IOI and elsewhere. It really exemplifies why informatics is special and very different from olympiad math and such.

Since $$$1 ≤ a_i ≤ 26$$$, we can assign each value from $$$1$$$ to $$$26$$$ to a letter a-z.

347267664

Using $$$7$$$ characters, we can encode $$$26^7 \approx 8 \cdot 10^9$$$ possibilities. For each number in the array, encode into a $$$7$$$-digit base-$$$26$$$ number. It is important to make sure each number takes up the same number of characters.

347268278

Let's try to solve the problem player B has to solve.

Let the range of a subarray be $$$max(p_l, p_{l+1}, ..., p_r) - min(p_l, p_{l+1}, ..., p_r)$$$. A subarray has range $$$n-1$$$ iff it contains both $$$1$$$ and $$$n$$$. We can binary search on the shortest prefix with range $$$n-1$$$, this will find the latter position of $$$1$$$ or $$$n$$$. Also binary search on the shortest suffix with range $$$n-1$$$, this will find the former position of $$$1$$$ or $$$n$$$. Now we've found the position of $$$1$$$ and $$$n$$$, but we don't know which is which.

This is where player A comes in. If $$$1$$$ appears before $$$n$$$, he will send $$$0$$$; otherwise, he will send $$$1$$$. Now player B can figure out which is which.

347270351

Let's phrase the problem slightly differently.

• Player A has a binary string of length $$$15$$$, and he will send a binary string of length $$$20$$$.
• On the way, none or one of the bits get flipped.
• Given the altered string, $$$B$$$ must find the original binary string of length $$$15$$$.

The first $$$15$$$ bits ($$$s_{1..15}$$$) will be allocated for the original string, and the remaining $$$5$$$ bits will be used to reconstruct where the flip happened.

The next $$$4$$$ ($$$s_{15..19}$$$) will house the bitwise XOR of the all the positions in the original string that are 1. The last bit ($$$s_{20}$$$) will be the number of bits in previous $$$4$$$ bits mod $$$2$$$.

Now there are $$$2$$$ cases:

Case 1: A flip happens in $$$s_{16..20}$$$

We can detect this case by checking if the last bit matches what it's supposed to be. If it doesn't, a flip has happened somewhere in the last $$$5$$$ bits. In this case, the original $$$15$$$ are completely untouched.

Case 2: A flip doesn't happen or happens in $$$s_{1..15}$$$

Here, we calculate the bitwise XOR of all the 1 in $$$s_{1..15}$$$. Let $$$x$$$ be this value and $$$y$$$ be the number stored in $$$s_{16..19}$$$. The cool thing is: $$$x \bigoplus y$$$ will be the position of the flipped bit, or $$$0$$$ if no flip occurred. This is because if a flip occured at position $$$k$$$, $$$x$$$ becomes $$$x \bigoplus k$$$.

347273446

For each value $$$x$$$, we can include $$$0$$$ or $$$1$$$. If $$$f(x)$$$ is the number of times $$$x$$$ appears in the array, Then there are $$$f(x) + 1$$$ ways to pick $$$0$$$ or $$$1$$$ occurrences of $$$x$$$. Since every value is independent of every other values, we will take the product of $$$f(x) + 1$$$ over all $$$x$$$. This can be done with std::map or sorting.

Let $$$L_i$$$ be the nearest greater element on the left, and $$$R_i$$$ be the nearest greater element on the right. These can be calculated in $$$\mathcal{O}(n)$$$ with monotonic stack.

From the value $$$i$$$ we can go to any value in $$$[L_i + 1, R_i - 1]$$$ that's strictly smaller than $$$h_i$$$. So we will calculate the DP in increasing order of $$$h_i$$$. The formula will be:

We can calculate this with a segment tree. We also have to take care of duplicates by calculating them at the same time and then updating the segment tree.

There are plenty of solutions that are straight-forward greedy, but I will describe a nice solution that uses DP.

The most obvious DP is $$$dp(i, j)$$$ being the lexicographically smallest string if you start in the cell $$$(i, j)$$$. Obviously, $$$dp(i, j) = A_{i,j} + min(dp(i+1, j), dp(i, j+1))$$$. Unfortunately, this is $$$\mathcal{O}(n^3)$$$, since each string can be of length $$$n$$$. We need to somehow find a way to compare strings without storing them. The way to fix this is: compression!

Now instead of calculating $$$dp(i, j)$$$, we will calculate $$$ord(i, j)$$$, which will just be an integer satisfying the following condition:

for all $(i_1, j_1), (i_2, j_2)$ in the same diagonal.

To calculate some diagonal, we will take each cell $$$(i, j)$$$ and sort them according to $$$(A_{i,j}, min(ord(i+1,j), ord(i,j+1))$$$. $$$ord(i, j)$$$ will simply be the position of $$$(i, j)$$$ according to the sort.

This is $$$\mathcal{O}(n^2 \log n)$$$ using std::sort, and it gets TLE. However the log can be removed using radix sort.

Let $$$P_i$$$ be the nearest greater element on the right. This can be calculated with monotonic stack. Now the query becomes: "How many times can you perform the assignment $$$l = P_l$$$ while $$$l \le r$$$?". This can be solved with binary lifting.

This can be solved using merge sort tree. In each node of the segment tree, we will store all the elements in the range in nondecreasing order.

For each query, we will decompose it into $$$\mathcal{O}(\log n)$$$ nodes, and each node, we will count the number of values between $$$c$$$ and $$$d$$$ in $$$\mathcal{O}(\log n)$$$ using binary search. This way, we can answer each query in $$$\mathcal{O}(\log^2 n)$$$, which is fast enough.

Let $$$S_i$$$ be the nearest equal element on the right, or $$$∞$$$. If there's an $$$i$$$ in $$$[l, r]$$$ such that $$$P_i \le r$$$, then $$$a_i = a_{P_i}$$$. That means not all values in $$$[l, r]$$$ are distinct. To check if such $$$i$$$ exists in $$$[l, r]$$$, check the minimum $$$P_i$$$. This can be done with a segment tree.

In each update, $$$\mathcal{O}(1)$$$ values change, so it can done in $$$\mathcal{O}(\log n)$$$ per query.

The average prime gap is $$$\mathcal{O}(\log n)$$$. So the trivial solution actually works in $$$\mathcal{O}(\sqrt{n} \log n)$$$. It can also be done in $$$\mathcal{O}(\log n)$$$ using randomized primality checks.

Imagine a functional graph with $$$n$$$ edges of the form $$$i \rightarrow p_i$$$. Let $$$L_1, L_2, ..., L_k$$$. The answer will be LCM(L_1, L_2, ..., L_k). This can be calculated by factorizing in $$$\mathcal{O}(n \sqrt{n})$$$ or $$$\mathcal{O}(n \log n)$$$ with sieve.

This can be done with monotonic queue, which allows adding an element at the back, removing the element from the front, and extracting the minimum. https://cp-algorithms.com/data_structures/stack_queue_modification.html#queue-modification-method-1

This can be done with a std::map to maintain the frequency of each value.

This can be done with a std::map to maintain the frequency of each value, as we as a std::set containing (frequency, values) pairs.

This can be done with an array to maintain the frequency of each value (since only values $$$\le k$$$ are relevant for th mex), as well as a std::set of excluded values.

This can be done by maintaining the number of inversions and an ordered set.

When adding a new element $$$x$$$, we will add the number of elements greater than $$$x$$$ to the inversion counter (since $$$x$$$ is at the end of the subarray).

When removing an element $$$x$$$, we will subtract the number of elements less than $$$x$$$ to the inversion counter (since $$$x$$$ is at the start of the subarray).

Distinct values, mode, MEX, and inversions can all be solved using a segment tree and coordinate compression.

We can use mergesort. This uses $$$n \log n$$$ queries.

Let's query chair $$$1$$$ and chair $$$N$$$. If they're equal, then we have found a solution. Otherwise, we can solve using binary search.

Let's query chair $$$x = \frac{N+1}{2}$$$. If $$$x$$$ is odd and chair $$$1$$$ is equal to chair $$$x$$$, we can guarantee a solution in $$$[x, n]$$$. Same can be said if $$$x$$$ is even and chair $$$1$$$ is not equal to chair $$$x$$$. Otherwise, there always exists a solution in $$$[1, x]$$$.

This solution uses exactly $$$2 + \lceil \log_2 n \rceil$$$ queries, which is at most $$$20$$$.

There exists a path between $$$u$$$ and $$$v$$$ of length $$$w$$$ iff the shortest path between $$$u$$$ and $$$v$$$ with the same parity $$$w' \le w$$$.

Construct a graph with $$$2N$$$ nodes, each node representing a pair (node, parity of path length). For each edge $$$(u, v)$$$ we will add undirected edges between $$$(u, 0), (v, 1)$$$, and $$$(u, 1), (v, 0)$$$.

Now for a query $$$(u, v, w)$$$, we have to check if the shortest path between $$$(u, 0)$$$ and $$$(v, w \mod 2)$$$ has length less than or equal to $$$w$$$. These distances can be precalculated in $$$\mathcal{O}(n (n + m))$$$ with BFS.

For each $$$i$$$, let $$$P_i$$$ be the number of $$$j$$$ such that $$$j \lt i$$$ and $$$x_j \gt x_i$$$. The answer will be the maximum $$$P_i$$$, since during each round, $$$P_i$$$ decreases by $$$1$$$ for each $$$P_i \gt 0$$$.

Let's consider each prime factor of $$$k$$$ separately.

Let's say that we want to calculate the number of ways to place the prime $$$p$$$. Let's say the number of times $$$p$$$ appears in the factorization of $$$a_i$$$ is $$$c_i$$$. The condition from the statement is equivalent to $$$\max(c_i, c_{i+1}) = X$$$, where $$$X$$$ is the number of times $$$p$$$ appears in the factorization of $$$k$$$.

Let $$$dp_p(n)$$$ be the number of arrays $$$c$$$ of length $$$n$$$ such that $$$\max(c_i, c_{i+1}) = X$$$. There are two cases:

• $$$c_n = X$$$

• $$$0 ≤ c_n \lt X, c_{n-1} = X$$$

So $$$dp_p(n) = dp_p(n-1) + dp_p(n-2) \cdot X$$$. $$$dp_p(n)$$$ can be calculated by raising a matrix to the $$$n$$$-th power in $$$mathcal{O}(\log n)$$$.

We can calculate this for each prime and multiply them to get the final answer, since the primes are independent of each other.

Subtract $$$a$$$ from each value in the array. Now we must count the number of subsets with sum $$$0$$$. This can be done easily with DP.

$$$dp(i, sum)$$$ is the number of subsets of $$$x_1, x_2, ..., x_i$$$ that add up to 0. Obviously $$$dp(i, sum) = dp(i-1, sum) + dp(i-1, sum - x_i)$$$.

We can handle negative value sums by sorting the array decreasingly so that the sum never goes below $$$0$$$. The final answer is $$$dp(n, 0)$$$.

We can do binary search on answer.

To check if the answer is at least $$$x$$$, subtract $$$x$$$ from each value in the array. Now we have to choose two prefixes that add up to at least $$$0$$$. We greedily take the biggest prefix sum of $$$a$$$ and $$$b$$$.

Also, $$$x$$$ doesn't have to be an integer.

We will calculate $$$dp(k)$$$, which is the number of subsets with GCD being $$$k$$$.

$$$dp(k)$$$ will be all the subsets of elements that are divisible by $$$k$$$, subtracting the subsets that have GCD being greater than $$$k$$$, i.e. $$$2k, 3k$$$, so on. Therefore:

This seems like it's $$$\mathcal{O}(n^2)$$$ but in reality it's $$$\mathcal{O}(n \log n)$$$.

We will use induction.

$$$2$$$ can be represented as $$$2$$$. $$$3$$$ can be represented as $$$3$$$. Now I will show that if we can represent $$$x$$$ and $$$x+1$$$, we can represent $$$x+2$$$ and $$$x+3$$$. We can use the fact that $$$x + 2 = (x) + 2$$$, and $$$x + 3 = (x+1) + 2$$$. To represent $$$x + 2$$$, we can take the representation of $$$x$$$ and append $$$2$$$. The same thing can be done with $$$x + 3$$$. QED.

We can use the Chicken McNugget Theorem. (Yes). It states that for a pair of coprime positive integers $$$m, n$$$, the largest number that cannot be represented as $$$am + bn$$$ for non-negative integers $$$a, b$$$ is $$$mn - m - n$$$. Applying the formula with $$$m = 2$$$ and $$$n = 3$$$, we get $$$2 \cdot 3 - 2 - 3 = 6 - 5 = 1$$$. Therefore, any integer greater than $$$1$$$ can be expressed. Read more: https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem

Let's say we have a subarray of length $$$k \gt 3$$$ with a negative sum. We can split this subarray into two subarrays: one of length $$$2$$$, the other of length $$$k - 2$$$. Since the sum of all the elements is negative, then at least one of these two subarrays has a negative sum.

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC target("popcnt")
using namespace __gnu_pbds;
using namespace std;
template<typename T> using ordered_set = tree<T, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update>;
#define popcount __builtin_popcountll
#define all(a) (a).begin(), (a).end()

vector<int> adj[200'000];
int dp[200'000], ans = -1000;

void dfs(int u = 0, int p = -1) {
    int mx1 = 0, mx2 = 0;
    for (int v : adj[u]) if (v != p) {
        dfs(v, u);
        if (dp[v] >= mx1) {
            swap(mx1, mx2);
            mx1 = dp[v];
        } else mx2 = max(mx2, dp[v]);
    }
    dp[u] = mx1 + adj[u].size() - 2;
    ans = max(ans, mx1 + mx2 + (int)adj[u].size() - 2);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n; cin >> n;
    for (int i = 0; i < n-1; i++) {
        int u,v; cin >> u >> v;
        adj[--u].push_back(--v);
        adj[v].push_back(u);
    }
    dfs();
    ans += 2;
    int leaves = 0;
    for (int i = 0; i < n; i++) leaves += adj[i].size() == 1;
    if (leaves >= n-1) ans--;
    cout << ans;
}