Skip to Content
CTRL K

Independent Set

Explicación

Enraizamos el árbol en el nodo 11, lo que nos permite definir el subárbol de cada nodo. Sea dp0[v]dp_0[v] la cantidad de formas de pintar el subárbol tales que vv esté pintado de blanco. De forma análoga, sea dp1[v]dp_1[v] la cantidad de formas de pintar el subárbol tales que vv esté pintado de negro.

Pintado de blanco

La cantidad de formas de pintar un subárbol de modo que el nodo raíz esté pintado de blanco es el producto de las formas de pintar los subárboles de los hijos. La cantidad de formas de pintar el subárbol de un hijo es la suma de pintarlo de blanco y de pintarlo de negro, es decir, dp0[u]+dp1[u]dp_0[u] + dp_1[u]. Así, la transición es:

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

Pintado de negro

Como no puede haber dos nodos adyacentes pintados ambos de negro, si el nodo raíz del subárbol está pintado de negro, ninguno de sus hijos puede estar pintado de negro. Esto nos lleva a la conclusión de que la cantidad de formas de pintar un subárbol de modo que el nodo raíz esté pintado de negro es el producto de todas las formas en que los subárboles de los hijos pueden pintarse de blanco.

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

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

#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;
	for (int v : adj[i]) {
		if (v != p) {
			dfs(v, i);
			dp[0][i] = (dp[0][i] * (dp[0][v] + dp[1][v])) % MOD;
		}
	}
	for (int v : adj[i]) {
		if (v != p) { dp[1][i] = (dp[1][i] * dp[0][v]) % MOD; }
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		adj[u].push_back(v), adj[v].push_back(u);
	}
	dfs(0, -1);
	cout << (dp[0][0] + dp[1][0]) % MOD << '\n';
	return 0;
}
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 {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(r.readLine());
		visited = new boolean[N];
		adj = new ArrayList[N];
		dp = new long[2][N];
 
		for (int i = 0; i < N; i++) { adj[i] = new ArrayList<>(); }
 
		for (int i = 0; i < N - 1; i++) {
			StringTokenizer st = new StringTokenizer(r.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			adj[a].add(b);
			adj[b].add(a);
		}
 
		dfs(0, -1);
 
		/*
		 * Devolvemos la cantidad de formas de que la raíz sea negra,
		 * sumada a la cantidad de formas de que la raíz sea blanca.
		 */
		System.out.println((dp[0][0] + dp[1][0]) % MOD);
	}
 
	public static void dfs(int node, int par) {
		dp[0][node] = 1;
		dp[1][node] = 1;
 
		// El nodo está pintado de blanco.
		for (int next : adj[node]) {
			if (next != par) {
				dfs(next, node);
				// Cantidad de formas de pintar el subárbol.
				long subtree = (dp[0][next] + dp[1][next]);
				dp[0][node] = (dp[0][node] * subtree) % MOD;
			}
		}
 
		// El nodo está pintado de negro.
		for (int next : adj[node]) {
			if (next != par) {
				// Si este nodo es negro, ninguno de los hijos puede ser negro.
				dp[1][node] = (dp[1][node] * dp[0][next]) % MOD;
			}
		}
	}
}
# para evitar Runtime Error con la recursión en Python
from sys import setrecursionlimit
 
setrecursionlimit(10**9)
 
n = int(input())
MOD = 10**9 + 7
 
# representamos el árbol con una lista de adyacencia
adj = [[] for i in range(n)]
 
for i in range(n - 1):
	x, y = map(int, input().split())
	x -= 1
	y -= 1
	adj[x].append(y)
	adj[y].append(x)
 
# 0 es blanco
# 1 es negro
 
dp = [[0] * 2 for i in range(n)]
 
 
def dfs(u, parent):
	dp[u][0] = dp[u][1] = 1
	for v in adj[u]:  # recorremos la lista de adyacencia del nodo u
		if v != parent:  # v debe ser hijo de u, no su padre
			dfs(v, u)  # calculamos recursivamente los valores de DP del hijo v
			# acumulamos los valores de DP de los hijos en el DP del nodo u
			# no olvidar tomar los valores módulo 1e9+7
			dp[u][1] *= dp[v][0]
			dp[u][1] %= MOD
			dp[u][0] *= (dp[v][0] + dp[v][1]) % MOD
			dp[u][0] %= MOD
 
 
dfs(0, -1)
 
ans = (dp[0][0] + dp[0][1]) % MOD
print(ans)
Fundamentos