1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1e5 + 8;
struct Edge {
    int to, next;
} edges[MAXN << 1];
int n, tot, heads[MAXN], vis[MAXN], ans;
inline void addEdge(int u, int v) {
    edges[tot].to = v;
    edges[tot].next = heads[u];
    heads[u] = tot++;
}
int dfs(int root) {
    vis[root] = 1;
    int n_childs = 0, odd_cnt = 0;
    for (int e = heads[root]; ~e; e = edges[e].next) {
        int t = edges[e].to;
        if (!vis[t]) {
            ++n_childs;
            int ret = dfs(t);
            if (ret % 2) odd_cnt += 1;
        }
    }
    ans += n_childs - odd_cnt;
    return (odd_cnt + 1) % 2 == 0 ? 0 : 1;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX