Official Editorial (Java)

Explanation

Define $\texttt{dp}[i][j]$ as the number of paintings for the subtree of barn $i$ with color $j$. Then, our transition for a vertex $v$ where $e$ iterates over the subtrees of $v$ is:

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
 Code Snippet: C++ Short Template (Click to expand)

const int mx = 1e5 + 1, MOD = 1e9 + 7;

ll dp[mx][3];
vi adj[mx];

void dfs(int v, int p = 0) {
	for (const int &e : adj[v]) {
		if (e != p) {