POI 2016 - Parade

Time Complexity: $\mathcal O(N)$.

We want to find a path in the tree with the maximum number of adjacent edges that aren't part of the path.

Any simple path in a rooted tree follows one of two general shapes:

1. It only goes up toward the root (from the lowest to the highest node in the path).
2. It goes up toward the root and then down again.

Since each path has a single highest node, we can check for each node $v$, what the best paths are for each case if $v$ is the highest node in that path. We will do this with dynamic programming.

Let $dp_1[v]$ and $dp_2[v]$ be the maximum number of adjacent edges for each case with $v$ as the highest node. If $C$ is the set of children of $v$, then the following recurrences hold:

1. $dp_1[v] = \max_{u \in C}(dp_1[u]) + (\text{Degree of }v) - 2$
2. $dp_2[v] = \max_{u \neq w \in C}(dp_1[u] + dp_1[w]) + (\text{Degree of }v) - 3$

We can calculate both of these values efficiently by keeping track of the two best values of $dp_1[u]$ while iterating through $C$.

Since the path must have a non-zero length though, we also need to subtract 1 from the answer if the graph is a star (i.e. a tree with $N - 1$ leaves).

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

vector<int> graph[200001];
int dp[2][200001];

void dfs(int node = 1, int parent = 0) {
	int mx1 = 1, mx2 = 1;
	for (int i : graph[node])
		if (i != parent) {