DP en árboles - Introducción

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int, int>;
#define f first
#define s second
#define mp make_pair
void setIO(string name = "") {  // name no vacío para E/S por archivos de USACO
	ios_base::sync_with_stdio(0);
	cin.tie(0);  // ver Fast Input & Output
	if (sz(name)) {
		freopen((name + ".in").c_str(), "r", stdin);  // ver Input & Output
		freopen((name + ".out").c_str(), "w", stdout);
	}
}
 
vi adj[200005];
int dp[200005][2];
 
void dfs(int v, int p) {
	for (int to : adj[v]) {
		if (to != p) {
			dfs(to, v);
			dp[v][0] += max(dp[to][0], dp[to][1]);
		}
	}
	for (int to : adj[v]) {
		if (to != p) {
			dp[v][1] =
			    max(dp[v][1], dp[to][0] + 1 + dp[v][0] - max(dp[to][0], dp[to][1]));
		}
	}
}
 
int main() {
	setIO();
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		adj[u].pb(v), adj[v].pb(u);
	}
	dfs(0, -1);
	cout << max(dp[0][0], dp[0][1]) << '\n';
}

import java.io.*;
import java.util.*;
 
public class TreeMatching {
	static ArrayList<Integer> adj[];
	static int dp[][];
	static void dfs(int v, int p) {
		for (int to : adj[v]) {
			if (to != p) {
				dfs(to, v);
				dp[v][0] += Math.max(dp[to][0], dp[to][1]);
			}
		}
		for (int to : adj[v]) {
			if (to != p) {
				dp[v][1] = Math.max(dp[v][1], dp[to][0] + 1 + dp[v][0] -
				                                  Math.max(dp[to][0], dp[to][1]));
			}
		}
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		adj = new ArrayList[N];
		dp = new int[N][2];
		for (int i = 0; i < N; ++i) { adj[i] = new ArrayList<Integer>(); }
		for (int i = 0; i < N - 1; ++i) {
			StringTokenizer st = new StringTokenizer(br.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);
		System.out.println(Math.max(dp[0][0], dp[0][1]));
	}
}

int n;
vi adj[MX];
bool done[MX];
int ans = 0;
 
void dfs(int pre, int cur) {
	for (int i : adj[cur]) {
		if (i != pre) {
			dfs(cur, i);
			if (!done[i] && !done[cur]) done[cur] = done[i] = 1, ans++;
		}
	}
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	F0R(i, n - 1) {
		int a, b;
		cin >> a >> b;
		adj[a].pb(b), adj[b].pb(a);
	}
	dfs(0, 1);
	cout << ans;
}

import java.io.*;
import java.util.*;
 
public class TreeMatching {
	static ArrayList<Integer> adj[];
	static int N;
	static boolean done[];
	static int ans = 0;
	static void dfs(int v, int p) {
		for (int to : adj[v]) {
			if (to != p) {
				dfs(to, v);
				if (!done[to] && !done[v]) {
					done[v] = done[to] = true;
					++ans;
				}
			}
		}
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		adj = new ArrayList[N];
		done = new boolean[N];
		for (int i = 0; i < N; ++i) { adj[i] = new ArrayList<Integer>(); }
		for (int i = 0; i < N - 1; ++i) {
			StringTokenizer st = new StringTokenizer(br.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);
		System.out.println(ans);
	}
}