Official Analysis (Offline)

To solve this problem online, we need efficiently find the closest ancestor of a farm $x$ with a certain milk type. Here are several ways to do this.

Method 1

Run the same DFS mentioned in the analysis. For each milk type, store the Euler tour indices at which the answer changes. Then we can get the answer for a vertex using a single lower_bound operation on the vector for the corresponding milk type.

Implementation

Time Complexity: $\mathcal{O}(\log N)$ per query.

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

const int MOD = 1000000007;
const int MX = 200005;

int T[MX];

template <int SZ> struct LCA {
	static const int BITS = 32 - __builtin_clz(SZ);

Method 2

Generate a persistent array for each vertex where the indices of the array correspond to the milk types.

Time Complexity: $\mathcal{O}(\log N)$ per query. Apparently this is doable in $\mathcal{O}(\log \log N)$ per query (paper). Is this bound optimal for this problem?

Method 3

Use HLD. We can check whether there exists a farm in the path from a vertex $x$ to the root of the heavy path containing $x$ ($\texttt{root}[x]$) with the desired milk type in $\mathcal{O}(1)$ time using an unordered map. Note that we only need to do two upper_bound operations per query.

In the solution below, I refer to milk types as "colors."

Implementation

Time Complexity: $\mathcal{O}(\log N)$ per query.

Copy
#include <algorithm>
#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>

/**
 * Description: Heavy-Light Decomposition, add val to verts
 * and query sum in path/subtree.
 * Time: any tree path is split into $\mathcal{O}(\log N)$ parts