stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

 

int n, x, y, res, fir=1, rt, f[101000];

vector<int>G[101000];

 

void dfs(int x,int fff){

  int isrt=0;

  if (G[x].size()>2&&fir) fir=0, isrt=1;

  for (auto y:G[x]) if (y!=fff) dfs(y,x);

  int t=max(0,(int)G[x].size()+isrt-2-f[x]);

  f[fff]+=!!f[x]|!!t;

  res+=t;

}

 

int main(){

  cin>>n;

  for (int i=n-1;i--;){

    scanf("%d%d",&x,&y); ++x; ++y;

    G[x].push_back(y); G[y].push_back(x);

  }

  for (rt=1;G[rt].size()!=1;++rt); dfs(rt,0);

  cout<<max(res,1);

}

// Faster C++ solution for the same problem (measured speedup: 18.8963531510702x):
#include<cmath>

#include<cstdio>

#include<algorithm>

using namespace std;

struct node{

	int ne,tow;

};

node pth[200000+10];

int mp[100000+10],szp;

int vis[100000+10];

int n;

int deg[100000+10];

int root=-1;

int son[100000+10];

int bro[100000+10];

int dp[100000+10];

int left[100000+10];

void addpath(int i,int j){

	++szp;

	pth[szp].ne=mp[i];

	pth[szp].tow=j;

	mp[i]=szp;

	deg[i]++;

}



void dfs1(int i,int j){

	if (vis[i]!=0) return;

	vis[i]=j;

	int po=mp[i];

	while (po!=-1){

		if (vis[pth[po].tow]==0){

			bro[pth[po].tow]=son[i];

			son[i]=pth[po].tow;

		}

		dfs1(pth[po].tow,j+1);

		po=pth[po].ne;

	}	

}

void dfs2(int i){

	int j=son[i];

	if (j==-1){

		left[i]=1;

		dp[i]=1;

		return;

	}

	while (j!=-1){

		dfs2(j);

		left[i]+=left[j];

		dp[i]+=dp[j];

		j=bro[j];

	}

	j=son[i];

	if (j!=-1&&bro[j]!=-1)

	while (j!=-1){

		if (dp[j]==1&&left[j]==1){

			dp[i]--;

			return;

		}

		j=bro[j];

	}



}





int main(){

	scanf("%d",&n);

	for (int f1=0;f1<n;f1++){

		mp[f1]=-1;

		vis[f1]=0;

	}

	

	for (int f1=1;f1<n;f1++){

		int i,j;

		scanf("%d%d",&i,&j);

		addpath(i,j);

		addpath(j,i);

		if (deg[i]>2)root=i;

		if (deg[j]>2)root=j;

	}

	if (root==-1){

		printf("1\n");

		return 0;

	}

	for (int f1=0;f1<n;f1++){

		son[f1]=-1;

		bro[f1]=-1;

		left[f1]=0;

		dp[f1]=0;

	}

	dfs1(root,1);

	dfs2(root);

	printf("%d\n",dp[root]);

	//for (int f1=0;f1<n;f1++)printf("%d ",dp[f1]);

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n;

struct Edge {

	int to;

	int next;

}edge[N * 2];

int head[N];

int cnt;

void AddEdge(int fr, int to) {

	edge[++cnt].to = to;

	edge[cnt].next = head[fr];

	head[fr] = cnt;

}

int d[N];

int DFS(int x, int fa) {

	int t = d[x] - 1;

	if (fa != 0) t--;

	int re = 0;

	for (int i = head[x]; i; i = edge[i].next) {

		if (edge[i].to != fa) {

			int tmp = DFS(edge[i].to, x);

			re += tmp;

			if (tmp) t--;

		}

	}

	re += max(t, 0);

	//cerr << x << " " << re << endl;

	return re;

}

int main() {

	scanf("%d", &n);

	for (int a, b, i = 1; i < n; i++) {

		scanf("%d%d", &a, &b);

		d[++a]++;

		d[++b]++;

		AddEdge(a, b);

		AddEdge(b, a);

	}

	for (int i = 1; i <= n; i++) {

		if (d[i] > 2) {

			printf("%d\n", DFS(i, 0));

			return 0;

		}

	}

	printf("1\n");

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.264648839453751x):
#include<cmath>

#include<cstdio>

#include<algorithm>

using namespace std;

struct node{

	int ne,tow;

};

node pth[200000+10];

int mp[100000+10],szp;

int vis[100000+10];

int n;

int deg[100000+10];

int root=-1;

int son[100000+10];

int bro[100000+10];

int dp[100000+10];

int left[100000+10];

void addpath(int i,int j){

	++szp;

	pth[szp].ne=mp[i];

	pth[szp].tow=j;

	mp[i]=szp;

	deg[i]++;

}



void dfs1(int i,int j){

	if (vis[i]!=0) return;

	vis[i]=j;

	int po=mp[i];

	while (po!=-1){

		if (vis[pth[po].tow]==0){

			bro[pth[po].tow]=son[i];

			son[i]=pth[po].tow;

		}

		dfs1(pth[po].tow,j+1);

		po=pth[po].ne;

	}	

}

void dfs2(int i){

	int j=son[i];

	if (j==-1){

		left[i]=1;

		dp[i]=1;

		return;

	}

	while (j!=-1){

		dfs2(j);

		left[i]+=left[j];

		dp[i]+=dp[j];

		j=bro[j];

	}

	j=son[i];

	if (j!=-1&&bro[j]!=-1)

	while (j!=-1){

		if (dp[j]==1&&left[j]==1){

			dp[i]--;

			return;

		}

		j=bro[j];

	}



}





int main(){

	scanf("%d",&n);

	for (int f1=0;f1<n;f1++){

		mp[f1]=-1;

		vis[f1]=0;

	}

	

	for (int f1=1;f1<n;f1++){

		int i,j;

		scanf("%d%d",&i,&j);

		addpath(i,j);

		addpath(j,i);

		if (deg[i]>2)root=i;

		if (deg[j]>2)root=j;

	}

	if (root==-1){

		printf("1\n");

		return 0;

	}

	for (int f1=0;f1<n;f1++){

		son[f1]=-1;

		bro[f1]=-1;

		left[f1]=0;

		dp[f1]=0;

	}

	dfs1(root,1);

	dfs2(root);

	printf("%d\n",dp[root]);

	//for (int f1=0;f1<n;f1++)printf("%d ",dp[f1]);

}
// Slower C++ solution:
#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

const int MAXN = 100000;

vector<int>G[MAXN + 5];

void addedge(int u, int v) {

	G[u].push_back(v);

	G[v].push_back(u);

}

int dp[MAXN + 5];

void dfs(int rt, int pre) {

	int cnt = 0;bool flag = 0;

	for(int i=0;i<G[rt].size();i++)

		if( G[rt][i] != pre ) {

			int p = G[rt][i];

			dfs(p, rt);

			if( dp[p] == 0 ) {

				if( !flag ) flag = true;

				else dp[rt]++;

			}

			else

				dp[rt] += dp[p];

		}

}

int main() {

	int N, root = -1;

	scanf("%d", &N);

	for(int i=1;i<=N-1;i++) {

		int a, b;

		scanf("%d%d", &a, &b);

		addedge(a, b);

	}

	for(int i=0;i<N;i++)

		if( G[i].size() > 2 )

			root = i;

	if( root == -1 ) {

		printf("1\n");

		return 0;

	}

	dfs(root, -1);

	printf("%d\n", dp[root]);

}

// Faster C++ solution for the same problem (measured speedup: 18.269998222970372x):
#include<cmath>

#include<cstdio>

#include<algorithm>

using namespace std;

struct node{

	int ne,tow;

};

node pth[200000+10];

int mp[100000+10],szp;

int vis[100000+10];

int n;

int deg[100000+10];

int root=-1;

int son[100000+10];

int bro[100000+10];

int dp[100000+10];

int left[100000+10];

void addpath(int i,int j){

	++szp;

	pth[szp].ne=mp[i];

	pth[szp].tow=j;

	mp[i]=szp;

	deg[i]++;

}



void dfs1(int i,int j){

	if (vis[i]!=0) return;

	vis[i]=j;

	int po=mp[i];

	while (po!=-1){

		if (vis[pth[po].tow]==0){

			bro[pth[po].tow]=son[i];

			son[i]=pth[po].tow;

		}

		dfs1(pth[po].tow,j+1);

		po=pth[po].ne;

	}	

}

void dfs2(int i){

	int j=son[i];

	if (j==-1){

		left[i]=1;

		dp[i]=1;

		return;

	}

	while (j!=-1){

		dfs2(j);

		left[i]+=left[j];

		dp[i]+=dp[j];

		j=bro[j];

	}

	j=son[i];

	if (j!=-1&&bro[j]!=-1)

	while (j!=-1){

		if (dp[j]==1&&left[j]==1){

			dp[i]--;

			return;

		}

		j=bro[j];

	}



}





int main(){

	scanf("%d",&n);

	for (int f1=0;f1<n;f1++){

		mp[f1]=-1;

		vis[f1]=0;

	}

	

	for (int f1=1;f1<n;f1++){

		int i,j;

		scanf("%d%d",&i,&j);

		addpath(i,j);

		addpath(j,i);

		if (deg[i]>2)root=i;

		if (deg[j]>2)root=j;

	}

	if (root==-1){

		printf("1\n");

		return 0;

	}

	for (int f1=0;f1<n;f1++){

		son[f1]=-1;

		bro[f1]=-1;

		left[f1]=0;

		dp[f1]=0;

	}

	dfs1(root,1);

	dfs2(root);

	printf("%d\n",dp[root]);

	//for (int f1=0;f1<n;f1++)printf("%d ",dp[f1]);

}
// Slower C++ solution:
#include<iostream>

#include<fstream>

#include<sstream>

#include<algorithm>

#include<cstdio>

#include<cassert>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<string>

#include<deque>

#include<queue>

#include<vector>

#include<list>

#include<map>

#include<set>

#include<bitset>

#include<stack>

#include<iomanip>

#include<utility>

#include<functional>

using namespace std;

int n,root,mr;

vector<int> edge[100005];

long long dp[100005];

void dfs(int dep,int prev)

{

	long long y=0;

	for(int i=0;i<edge[dep].size();i++)

	{

		int x=edge[dep][i];

		if(x!=prev)

		{

			dfs(x,dep);

			dp[dep]+=dp[x];

			if(dp[x]==0)

				y++;

		}

	}

	dp[dep]+=max((long long)0,y-1);

}

int main()

{

	cin>>n;

	for(int i=0;i<n-1;i++)

	{

		int a,b;

		cin>>a>>b;

		edge[a].push_back(b);

		edge[b].push_back(a);

	}

	for(int i=0;i<n;i++)

		if(edge[i].size()>mr)

		{

			root=i;

			mr=edge[i].size();

		}

	dfs(root,-1);

	if(dp[root]==0)

		cout<<1;

	else

		cout<<dp[root];

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.5822883164549024x):
#include <bits/stdc++.h>

using namespace std;



const int maxn = 1e5 + 5;



int n, ans, cnt, root;

int tail[maxn], deg[maxn];

bool p[maxn];

struct edge

{

    int v, next;

}e[maxn << 1];



void ins(int u, int v)

{

    e[++cnt] = (edge){v, tail[u]};

    tail[u] = cnt;

}



void dfs(int u, int pa)

{

    int tot = deg[u] - (pa != 0);

    for(int i = tail[u]; i; i = e[i].next)

        if(e[i].v != pa)

        {

            dfs(e[i].v, u);

            p[u] |= p[e[i].v];

            tot -= p[e[i].v];

        }

    if(tot > 1)

    {

        ans += tot - 1;

        p[u] = 1;

    }

}



int main()

{

    int u, v;

    scanf("%d", &n);

    for(int i = 1; i < n; i++)

    {

        scanf("%d%d", &u, &v);

        u++, v++;

        ins(u, v);

        ins(v, u);

        deg[u]++, deg[v]++;

        if(deg[u] > 2)

            root = u;

        else if(deg[v] > 2)

            root = v;

    }

    if(!root)

        ans = 1;

    else

        dfs(root, 0);

    printf("%d\n", ans);

    return 0;

}
// Slower C++ solution:
/************************************************************************/

/****															*********/

/****                          Writer:孙~~                      *********/

/****                            Lang:C++                       *********/

/****                          Status:Unknow                    *********/

/****															*********/

/************************************************************************/

#include <iostream>

#include <string>

#include <cstdio>

#include <vector>

#include <queue>

#include <list>

#include <cstdlib>

#include <algorithm>

#include <set>

#include <map>

#include <deque>

#include <cstring>

#include <cmath>

//#include<bits/stdc++.h>

#define debug(...) if(debug) printf(__VA_ARGS__)

using namespace std;



const int INF=0x3f3f3f3f;

const int SIZE=100005;

const bool debug=false;



int dp[SIZE];

vector<int> mp[SIZE];

int dig[SIZE];



int n;



void visit(int p,int f){

	int s=0,cnt=0;

	for(int i=0;i<mp[p].size();i++){

		int u=mp[p][i];

		if(u==f) continue;

		visit(u,p);

		if(dp[u]==0) cnt++;

		s+=dp[u];

	}

//	if(p==1) debug("%d\n",leave);

	dp[p]=s+max(0,cnt-1);

}



int main(){

	scanf("%d",&n);

	for(int a,b,i=0;i<n-1;i++){

		scanf("%d",&a);

		scanf("%d",&b);

		mp[a].push_back(b);

		mp[b].push_back(a);

		dig[a]++;

		dig[b]++;

	}

	int root=-1,mx=0;

	for(int i=0;i<n;i++){

		if(dig[i]>mx) root=i,mx=dig[i];

	}

	if(mx<=2){

		puts("1");

		return 0;

	}

	visit(root,-1);

	for(int i=0;i<n;i++) debug("%d ",dp[i]);

	debug("\n");

	printf("%d\n",dp[root]);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.5648028425337084x):
#include <bits/stdc++.h>

using namespace std;



const int maxn = 1e5 + 5;



int n, ans, cnt, root;

int tail[maxn], deg[maxn];

bool p[maxn];

struct edge

{

    int v, next;

}e[maxn << 1];



void ins(int u, int v)

{

    e[++cnt] = (edge){v, tail[u]};

    tail[u] = cnt;

}



void dfs(int u, int pa)

{

    int tot = deg[u] - (pa != 0);

    for(int i = tail[u]; i; i = e[i].next)

        if(e[i].v != pa)

        {

            dfs(e[i].v, u);

            p[u] |= p[e[i].v];

            tot -= p[e[i].v];

        }

    if(tot > 1)

    {

        ans += tot - 1;

        p[u] = 1;

    }

}



int main()

{

    int u, v;

    scanf("%d", &n);

    for(int i = 1; i < n; i++)

    {

        scanf("%d%d", &u, &v);

        u++, v++;

        ins(u, v);

        ins(v, u);

        deg[u]++, deg[v]++;

        if(deg[u] > 2)

            root = u;

        else if(deg[v] > 2)

            root = v;

    }

    if(!root)

        ans = 1;

    else

        dfs(root, 0);

    printf("%d\n", ans);

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

 

int n, x, y, res, fir=1, rt, f[101000];

vector<int>G[101000];

 

void dfs(int x,int fff){

  int isrt=0;

  if (G[x].size()>2&&fir) fir=0, isrt=1;

  for (auto y:G[x]) if (y!=fff) dfs(y,x);

  int t=max(0,(int)G[x].size()+isrt-2-f[x]);

  f[fff]+=!!f[x]|!!t;

  res+=t;

}

 

int main(){

  cin>>n;

  for (int i=n-1;i--;){

    scanf("%d%d",&x,&y); ++x; ++y;

    G[x].push_back(y); G[y].push_back(x);

  }

  for (rt=1;G[rt].size()!=1;++rt); dfs(rt,0);

  cout<<max(res,1);

}

// Faster C++ solution for the same problem (measured speedup: 3.610228663524257x):
#include <bits/stdc++.h>

using namespace std;



const int maxn = 1e5 + 5;



int n, ans, cnt, root;

int tail[maxn], deg[maxn];

bool p[maxn];

struct edge

{

    int v, next;

}e[maxn << 1];



void ins(int u, int v)

{

    e[++cnt] = (edge){v, tail[u]};

    tail[u] = cnt;

}



void dfs(int u, int pa)

{

    int tot = deg[u] - (pa != 0);

    for(int i = tail[u]; i; i = e[i].next)

        if(e[i].v != pa)

        {

            dfs(e[i].v, u);

            p[u] |= p[e[i].v];

            tot -= p[e[i].v];

        }

    if(tot > 1)

    {

        ans += tot - 1;

        p[u] = 1;

    }

}



int main()

{

    int u, v;

    scanf("%d", &n);

    for(int i = 1; i < n; i++)

    {

        scanf("%d%d", &u, &v);

        u++, v++;

        ins(u, v);

        ins(v, u);

        deg[u]++, deg[v]++;

        if(deg[u] > 2)

            root = u;

        else if(deg[v] > 2)

            root = v;

    }

    if(!root)

        ans = 1;

    else

        dfs(root, 0);

    printf("%d\n", ans);

    return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

const int MAXN = 100000;

vector<int>G[MAXN + 5];

void addedge(int u, int v) {

	G[u].push_back(v);

	G[v].push_back(u);

}

int dp[MAXN + 5];

void dfs(int rt, int pre) {

	int cnt = 0;bool flag = 0;

	for(int i=0;i<G[rt].size();i++)

		if( G[rt][i] != pre ) {

			int p = G[rt][i];

			dfs(p, rt);

			if( dp[p] == 0 ) {

				if( !flag ) flag = true;

				else dp[rt]++;

			}

			else

				dp[rt] += dp[p];

		}

}

int main() {

	int N, root = -1;

	scanf("%d", &N);

	for(int i=1;i<=N-1;i++) {

		int a, b;

		scanf("%d%d", &a, &b);

		addedge(a, b);

	}

	for(int i=0;i<N;i++)

		if( G[i].size() > 2 )

			root = i;

	if( root == -1 ) {

		printf("1\n");

		return 0;

	}

	dfs(root, -1);

	printf("%d\n", dp[root]);

}

// Faster C++ solution for the same problem (measured speedup: 3.4905608897010514x):
#include <bits/stdc++.h>

using namespace std;



const int maxn = 1e5 + 5;



int n, ans, cnt, root;

int tail[maxn], deg[maxn];

bool p[maxn];

struct edge

{

    int v, next;

}e[maxn << 1];



void ins(int u, int v)

{

    e[++cnt] = (edge){v, tail[u]};

    tail[u] = cnt;

}



void dfs(int u, int pa)

{

    int tot = deg[u] - (pa != 0);

    for(int i = tail[u]; i; i = e[i].next)

        if(e[i].v != pa)

        {

            dfs(e[i].v, u);

            p[u] |= p[e[i].v];

            tot -= p[e[i].v];

        }

    if(tot > 1)

    {

        ans += tot - 1;

        p[u] = 1;

    }

}



int main()

{

    int u, v;

    scanf("%d", &n);

    for(int i = 1; i < n; i++)

    {

        scanf("%d%d", &u, &v);

        u++, v++;

        ins(u, v);

        ins(v, u);

        deg[u]++, deg[v]++;

        if(deg[u] > 2)

            root = u;

        else if(deg[v] > 2)

            root = v;

    }

    if(!root)

        ans = 1;

    else

        dfs(root, 0);

    printf("%d\n", ans);

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<fstream>

#include<sstream>

#include<algorithm>

#include<cstdio>

#include<cassert>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<string>

#include<deque>

#include<queue>

#include<vector>

#include<list>

#include<map>

#include<set>

#include<bitset>

#include<stack>

#include<iomanip>

#include<utility>

#include<functional>

using namespace std;

int n,root,mr;

vector<int> edge[100005];

long long dp[100005];

void dfs(int dep,int prev)

{

	long long y=0;

	for(int i=0;i<edge[dep].size();i++)

	{

		int x=edge[dep][i];

		if(x!=prev)

		{

			dfs(x,dep);

			dp[dep]+=dp[x];

			if(dp[x]==0)

				y++;

		}

	}

	dp[dep]+=max((long long)0,y-1);

}

int main()

{

	cin>>n;

	for(int i=0;i<n-1;i++)

	{

		int a,b;

		cin>>a>>b;

		edge[a].push_back(b);

		edge[b].push_back(a);

	}

	for(int i=0;i<n;i++)

		if(edge[i].size()>mr)

		{

			root=i;

			mr=edge[i].size();

		}

	dfs(root,-1);

	if(dp[root]==0)

		cout<<1;

	else

		cout<<dp[root];

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.5918761122208944x):
#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<iostream> 

using namespace std;

struct node{

	int y,next;

}road[200010];

int N,x,y,du[100010],cnt,head[100010],p;

bool vis[100010];

int read()

{

	static int x;

	static char ch;

	x = 0;

	for(ch=getchar();ch>'9'||ch<'0';ch=getchar());

	for(;ch>='0'&&ch<='9';ch=getchar()) x = x * 10 + ch - '0';

	return x;

}

void build(int x,int y)

{

	road[++p].y = y;

	road[p].next = head[x];

	head[x] = p;

}

int dfs(int x,int f)

{

	if (du[x] > 2) return x;

	for (int i = head[x];i;i=road[i].next) if (road[i].y!=f) return dfs(road[i].y,x);

	return x;

}

int main()

{

	N = read();

	for (int i = 1;i<N;++i)

	{

		x = read() + 1;

		y = read() + 1;

		build(x,y);

		build(y,x);

		du[x]++;du[y]++;

	}

	for (int i = 1;i<=N;++i) if (du[i]==1) cnt++,vis[dfs(i,0)] = true;

	for (int i = 1;i<=N;++i) if (vis[i]) cnt -- ;

	if (!cnt) cnt++;

	printf("%d\n",cnt);

	return 0;

}
// Slower C++ solution:
/************************************************************************/

/****															*********/

/****                          Writer:孙~~                      *********/

/****                            Lang:C++                       *********/

/****                          Status:Unknow                    *********/

/****															*********/

/************************************************************************/

#include <iostream>

#include <string>

#include <cstdio>

#include <vector>

#include <queue>

#include <list>

#include <cstdlib>

#include <algorithm>

#include <set>

#include <map>

#include <deque>

#include <cstring>

#include <cmath>

//#include<bits/stdc++.h>

#define debug(...) if(debug) printf(__VA_ARGS__)

using namespace std;



const int INF=0x3f3f3f3f;

const int SIZE=100005;

const bool debug=false;



int dp[SIZE];

vector<int> mp[SIZE];

int dig[SIZE];



int n;



void visit(int p,int f){

	int s=0,cnt=0;

	for(int i=0;i<mp[p].size();i++){

		int u=mp[p][i];

		if(u==f) continue;

		visit(u,p);

		if(dp[u]==0) cnt++;

		s+=dp[u];

	}

//	if(p==1) debug("%d\n",leave);

	dp[p]=s+max(0,cnt-1);

}



int main(){

	scanf("%d",&n);

	for(int a,b,i=0;i<n-1;i++){

		scanf("%d",&a);

		scanf("%d",&b);

		mp[a].push_back(b);

		mp[b].push_back(a);

		dig[a]++;

		dig[b]++;

	}

	int root=-1,mx=0;

	for(int i=0;i<n;i++){

		if(dig[i]>mx) root=i,mx=dig[i];

	}

	if(mx<=2){

		puts("1");

		return 0;

	}

	visit(root,-1);

	for(int i=0;i<n;i++) debug("%d ",dp[i]);

	debug("\n");

	printf("%d\n",dp[root]);

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.5743438393996625x):
#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<iostream> 

using namespace std;

struct node{

	int y,next;

}road[200010];

int N,x,y,du[100010],cnt,head[100010],p;

bool vis[100010];

int read()

{

	static int x;

	static char ch;

	x = 0;

	for(ch=getchar();ch>'9'||ch<'0';ch=getchar());

	for(;ch>='0'&&ch<='9';ch=getchar()) x = x * 10 + ch - '0';

	return x;

}

void build(int x,int y)

{

	road[++p].y = y;

	road[p].next = head[x];

	head[x] = p;

}

int dfs(int x,int f)

{

	if (du[x] > 2) return x;

	for (int i = head[x];i;i=road[i].next) if (road[i].y!=f) return dfs(road[i].y,x);

	return x;

}

int main()

{

	N = read();

	for (int i = 1;i<N;++i)

	{

		x = read() + 1;

		y = read() + 1;

		build(x,y);

		build(y,x);

		du[x]++;du[y]++;

	}

	for (int i = 1;i<=N;++i) if (du[i]==1) cnt++,vis[dfs(i,0)] = true;

	for (int i = 1;i<=N;++i) if (vis[i]) cnt -- ;

	if (!cnt) cnt++;

	printf("%d\n",cnt);

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

 

int n, x, y, res, fir=1, rt, f[101000];

vector<int>G[101000];

 

void dfs(int x,int fff){

  int isrt=0;

  if (G[x].size()>2&&fir) fir=0, isrt=1;

  for (auto y:G[x]) if (y!=fff) dfs(y,x);

  int t=max(0,(int)G[x].size()+isrt-2-f[x]);

  f[fff]+=!!f[x]|!!t;

  res+=t;

}

 

int main(){

  cin>>n;

  for (int i=n-1;i--;){

    scanf("%d%d",&x,&y); ++x; ++y;

    G[x].push_back(y); G[y].push_back(x);

  }

  for (rt=1;G[rt].size()!=1;++rt); dfs(rt,0);

  cout<<max(res,1);

}

// Faster C++ solution for the same problem (measured speedup: 3.6198912400777417x):
#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<iostream> 

using namespace std;

struct node{

	int y,next;

}road[200010];

int N,x,y,du[100010],cnt,head[100010],p;

bool vis[100010];

int read()

{

	static int x;

	static char ch;

	x = 0;

	for(ch=getchar();ch>'9'||ch<'0';ch=getchar());

	for(;ch>='0'&&ch<='9';ch=getchar()) x = x * 10 + ch - '0';

	return x;

}

void build(int x,int y)

{

	road[++p].y = y;

	road[p].next = head[x];

	head[x] = p;

}

int dfs(int x,int f)

{

	if (du[x] > 2) return x;

	for (int i = head[x];i;i=road[i].next) if (road[i].y!=f) return dfs(road[i].y,x);

	return x;

}

int main()

{

	N = read();

	for (int i = 1;i<N;++i)

	{

		x = read() + 1;

		y = read() + 1;

		build(x,y);

		build(y,x);

		du[x]++;du[y]++;

	}

	for (int i = 1;i<=N;++i) if (du[i]==1) cnt++,vis[dfs(i,0)] = true;

	for (int i = 1;i<=N;++i) if (vis[i]) cnt -- ;

	if (!cnt) cnt++;

	printf("%d\n",cnt);

	return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

const int MAXN = 100000;

vector<int>G[MAXN + 5];

void addedge(int u, int v) {

	G[u].push_back(v);

	G[v].push_back(u);

}

int dp[MAXN + 5];

void dfs(int rt, int pre) {

	int cnt = 0;bool flag = 0;

	for(int i=0;i<G[rt].size();i++)

		if( G[rt][i] != pre ) {

			int p = G[rt][i];

			dfs(p, rt);

			if( dp[p] == 0 ) {

				if( !flag ) flag = true;

				else dp[rt]++;

			}

			else

				dp[rt] += dp[p];

		}

}

int main() {

	int N, root = -1;

	scanf("%d", &N);

	for(int i=1;i<=N-1;i++) {

		int a, b;

		scanf("%d%d", &a, &b);

		addedge(a, b);

	}

	for(int i=0;i<N;i++)

		if( G[i].size() > 2 )

			root = i;

	if( root == -1 ) {

		printf("1\n");

		return 0;

	}

	dfs(root, -1);

	printf("%d\n", dp[root]);

}

// Faster C++ solution for the same problem (measured speedup: 3.499903182102667x):
#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<iostream> 

using namespace std;

struct node{

	int y,next;

}road[200010];

int N,x,y,du[100010],cnt,head[100010],p;

bool vis[100010];

int read()

{

	static int x;

	static char ch;

	x = 0;

	for(ch=getchar();ch>'9'||ch<'0';ch=getchar());

	for(;ch>='0'&&ch<='9';ch=getchar()) x = x * 10 + ch - '0';

	return x;

}

void build(int x,int y)

{

	road[++p].y = y;

	road[p].next = head[x];

	head[x] = p;

}

int dfs(int x,int f)

{

	if (du[x] > 2) return x;

	for (int i = head[x];i;i=road[i].next) if (road[i].y!=f) return dfs(road[i].y,x);

	return x;

}

int main()

{

	N = read();

	for (int i = 1;i<N;++i)

	{

		x = read() + 1;

		y = read() + 1;

		build(x,y);

		build(y,x);

		du[x]++;du[y]++;

	}

	for (int i = 1;i<=N;++i) if (du[i]==1) cnt++,vis[dfs(i,0)] = true;

	for (int i = 1;i<=N;++i) if (vis[i]) cnt -- ;

	if (!cnt) cnt++;

	printf("%d\n",cnt);

	return 0;

}