POI 2016 - Parade

Author: Andi Qu


Time Complexity: O(N)\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 vv, what the best paths are for each case if vv is the highest node in that path. We will do this with dynamic programming.

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

  1. dp1[v]=maxuC(dp1[u])+(Degree of v)2dp_1[v] = \max_{u \in C}(dp_1[u]) + (\text{Degree of }v) - 2
  2. dp2[v]=maxuwC(dp1[u]+dp1[w])+(Degree of v)3dp_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 dp1[u]dp_1[u] while iterating through CC.

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 N1N - 1 leaves).

#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) {

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!