AtCoder DP Contest - Independent Set

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

Root the tree at node $1$, allowing us to define the subtree of each node. Let $d{p}_0[v]$ represent the number of ways the subtree can be painted such that $v$ is painted white. Similarily, let $d{p}_1[v]$ represent the number of ways the subtree can be painted such that $v$ 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, $d{p}_0[u]+d{p}_1[u]$. 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.

1#include <iostream>
2#include <vector>
3using namespace std;
4
5int MOD = 1000000007;
6long dp[2][100000];
7vector<int> adj[100000];
8void dfs(int i, int p){
9    dp[0][i] = 1;
10    dp[1][i] = 1;