AtCoder DP Contest - Independent Set

Authors: Andrew Wang, Sofia Yang, Mohammad Nour Massri

Explanation

Root the tree at node 11, allowing us to define the subtree of each node. Let dp0[v]dp_0[v] represent the number of ways the subtree can be painted such that vv is painted white. Similarily, let dp1[v]dp_1[v] represent the number of ways the subtree can be painted such that vv is painted black.

Painted White

The number of ways to paint a subtree such that the root node is painted white is the product of the ways to paint the child subtrees. The number of ways to paint a child subtree is the sum of how to paint it white and how to paint it black or, dp0[u]+dp1[u]dp_0[u] + dp_1[u]. So the transition is:

dp0[v]=uchild(v)(dp0[u]+dp1[u]).dp_0[v] = \prod_{u \in child(v)} \left(dp_0[u]+ dp_1[u]\right).

Painted Black

Since no two adjacent nodes can both be painted black, if the root node of the subtree is painted black, none of its children can be painted black. This leads us to the conclusion that the number of ways to paint a subtree such that the root node is painted black is the product of all the ways the child subtrees can be painted white.

dp1[v]=uchild(v)dp0[u].dp_1[v] = \prod_{u \in child(v)} dp_0[u].

Implementation

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

C++

#include <iostream>
#include <vector>
using namespace std;
int MOD = 1000000007;
long dp[2][100000];
vector<int> adj[100000];
void dfs(int i, int p) {
dp[0][i] = 1;
dp[1][i] = 1;

Java

import java.io.*;
import java.util.*;
public class Main {
public static ArrayList<Integer>[] adj;
public static boolean[] visited;
public static long[][] dp;
public static final int MOD = (int)1e9 + 7;
public static void main(String[] args) throws IOException {

Python

# to solve Runtime Error problem with recursion in python
from sys import setrecursionlimit
setrecursionlimit(10**9)
n = int(input())
MOD = 10**9 + 7
# representing the tree in an adjacency list
adj = [[] for i in range(n)]

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!