代码

#include <cstdio>#include <cstring>#include <iostream>#define N 1000001int n, cnt;int head[N], to[N << 1], next[N << 1], size[N], cp[N];inline int read(){	int x = 0, f = 1;	char ch = getchar();	for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;	return x * f;}inline void add(int x, int y){	to[cnt] = y;	next[cnt] = head[x];	head[x] = cnt++;}inline void dfs(int u){	int i, v, rest;	rest = size[u] = 1;	for(i = head[u]; i ^ -1; i = next[i])	{		v = to[i];		if(!size[v])		{			dfs(v);			rest += size[v];			size[u] += size[v];			cp[u] += cp[v];			if(cp[v]) rest -= size[v];		}	}	cp[u] += rest >> 1;}int main(){	int i, x, y;	n = read();	memset(head, -1, sizeof(head));	for(i = 1; i < n; i++)	{		x = read();		y = read();		add(x, y);		add(y, x);	}	dfs(1);	printf("%d\n", cp[1]);	return 0;}