AtCoder DP Contest - Independent Set
Authors: Andrew Wang, Sofia Yang, Mohammad Nour Massri
Explanation
Root the tree at node , allowing us to define the subtree of each node. Let represent the number of ways the subtree can be painted such that is painted white. Similarily, let represent the number of ways the subtree can be painted such that 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, . So the transition is:
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.
Implementation
Time Complexity:
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 pythonfrom sys import setrecursionlimitsetrecursionlimit(10**9)n = int(input())MOD = 10**9 + 7# representing the tree in an adjacency listadj = [[] 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!