57 lines
978 B
C
57 lines
978 B
C
#include <stdio.h>
|
|
#include <stdbool.h>
|
|
|
|
#define MAX_N 1000000
|
|
|
|
int dp[MAX_N + 1][2];
|
|
bool visited[MAX_N + 1];
|
|
|
|
int head[MAX_N + 1];
|
|
int to[MAX_N * 2 + 1];
|
|
int next[MAX_N * 2 + 1];
|
|
int edge_cnt = 0;
|
|
|
|
void add_edge(int u, int v) {
|
|
edge_cnt++;
|
|
to[edge_cnt] = v;
|
|
next[edge_cnt] = head[u];
|
|
head[u] = edge_cnt;
|
|
}
|
|
|
|
int min(int a, int b) {
|
|
return a < b ? a : b;
|
|
}
|
|
|
|
void find(int node) {
|
|
visited[node] = true;
|
|
dp[node][1] = 1;
|
|
|
|
for(int e = head[node]; e != 0; e = next[e]) {
|
|
int child = to[e];
|
|
|
|
if(visited[child]) continue;
|
|
|
|
find(child);
|
|
dp[node][1] += min(dp[child][1], dp[child][0]);
|
|
dp[node][0] += dp[child][1];
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
int N;
|
|
if(scanf("%d", &N) != 1) return 0;
|
|
|
|
for(int i = 0; i < N - 1; i++) {
|
|
int u, v;
|
|
scanf("%d %d", &u, &v);
|
|
add_edge(u, v);
|
|
add_edge(v, u);
|
|
}
|
|
|
|
find(1);
|
|
|
|
printf("%d\n", min(dp[1][0], dp[1][1]));
|
|
|
|
return 0;
|
|
}
|