stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <vector>

const int Maxn=1e5+5;

#define rep(i,n) for (int i=0;i<n;++i)

#define int long long

int n,mx;

std::vector <int> v[Maxn];

int dp[Maxn];

void dfs(int k,int p=-1)

{

	int s=0;

	int ss=0;

	std::vector <int> t;

	for (auto &x:v[k])

	{

		if (x==p)

		{

			continue;

		}

		ss++;

		t.push_back(x);

		dfs(x,k);

		if (dp[x])

		{

			s++;

		}

		dp[k]+=dp[x];

	}

	dp[k]+=std::max(ss-s-1,0ll);

}

signed main()

{

	std::cin>>n;

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

	{

		int x,y;

		std::cin>>x>>y;

		v[x].push_back(y);

		v[y].push_back(x);

	}

	rep(i,n)

	{

		if (v[i].size()>v[mx].size())

		{

			mx=i;

		}

	}

	dfs(mx);

	std::cout<<std::max(1ll,dp[mx])<<std::endl;

	return 0;

}


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

using namespace std;

const int maxn = 1e5+100;

typedef long long LL;

int val[maxn],First[maxn],cnt,N,M,deg[maxn];

int tot,pre[maxn],rdeg[maxn];

int ans = 0;

struct node{

    int to,Next;

}Tree[maxn*2];

void init(){

    memset(First,-1,sizeof(First));

    cnt = 0;

}

void addedge(int from,int to){

    Tree[cnt].to = to;

    Tree[cnt].Next = First[from];

    First[from] = cnt++;

}

int dfs(int u,int fa){

    if(deg[u]==0)return 0;

    int shoud = deg[u] - 1;

    int bouns = 0;

    for(int i = First[u];i!=-1;i=Tree[i].Next){

        int to = Tree[i].to;

        if(to==fa)continue;

        deg[to]--;

        bouns+=dfs(to,u);

    }

    ans+=max(0,shoud-bouns);

    return bouns||(shoud-bouns);

}

int main(){

    init();

    scanf("%d",&N);

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

        int a,b;

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

        addedge(a,b);

        addedge(b,a);

        deg[a]++;

        deg[b]++;

    }

    int now = 0,max1 = 0;

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

            rdeg[i] = deg[i];

            if(deg[i]>max1){

                now = i;

                max1 = deg[i];

            }

    }

    dfs(now,-1);

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

    return 0;

}

/*

7

0 1

0 2

1 3

1 4

1 5

2 6



*/
// Slower C++ solution:
//dfs版 

#include<iostream>

#include<cctype>

#include<queue>

#include<cstdio>

#include<cmath>

#include<sstream>

#include<string>

#include<algorithm>

#include<cstring>

#include<vector>

#include<ctime>

#include<cstdlib>

#include<map>

#include<utility>

#include<iomanip>

#include<set>

#include<stack>

#define lowbit(i) ((i)&(-i))

using namespace std;

typedef long long ll;typedef pair<int,int> pii;

typedef pair<ll,ll> pll;typedef vector<string> vss;

typedef vector<int> vii;typedef vector<pii> vpi;

typedef vector<ll> vll;typedef vector<pll> vpl;typedef long double ld;

typedef unsigned long long ul;typedef queue<int> qii;typedef queue<pii> qpi;

int n,x,y,dp[100005],res,t;

vii v[100005];

int mx=0,deg[1000005];

qii q;

int main()

{

// 	freopen("","r",stdin);

// 	freopen("","w",stdout);

	cin>>n;

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

		cin>>x>>y;

		v[x].push_back(y);

		v[y].push_back(x);

		deg[x]++;

		deg[y]++;

	}

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

		if(v[i].size()>mx)

			mx=v[i].size();

	}

	if(mx<=2){

		puts("1");

		return 0;

	}

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

		if(deg[i]==1) q.push(i);

	}

	while(!q.empty()){

		int p=q.front(),to=-1;q.pop();

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

			to=v[p][i];

			if(deg[to]!=1) break;

		}

		if(deg[to]==2){

			deg[to]=1;

			q.push(to);

		}

	}

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

		if(deg[i]==1) continue;

		t=0;

		for(int j=0;j<v[i].size();j++){

			int to=v[i][j];

			if(deg[to]==1) t++;

		}

		res+=max(0,t-1);

	}

	cout<<res<<'\n';

	return 0;

}

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

#define maxl 100010



using namespace std;



int n,ans,cnt;

int ehead[maxl];

int du[maxl];

struct ed

{

	int to,nxt;

}e[maxl<<1];

bool vis[maxl];



inline void add(int u,int v)

{

	e[++cnt].to=v;e[cnt].nxt=ehead[u];ehead[u]=cnt;

}



inline void prework()

{

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

		vis[i]=false,ehead[i]=0,du[i]=0;

	int u,v;

	cnt=0;

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

	{

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

		u++;v++;

		add(u,v);du[v]++;

		add(v,u);du[u]++;

	}

}



inline int dfs(int u,int fa)

{

	int v;

	for(int i=ehead[u];i;i=e[i].nxt)

	{

		v=e[i].to;

		if(v==fa) continue;

		if(du[v]>2)

			return v;

		else

			return dfs(v,u);

	}

}



inline void mainwork()

{

	bool flag=true;

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

	if(du[i]>2)

		flag=false;

	if(flag)

	{

		ans=1;

		return;

	}

	ans=0;

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

	if(du[i]==1)

		vis[dfs(i,0)]=true,ans++;

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

	if(vis[i])

		ans--;

}



inline void print()

{

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

}



int main()

{

	while(~scanf("%d",&n))

	{

		prework();

		mainwork();

		print();

	}

	return 0;

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

#include <vector>

const int Maxn=1e5+5;

#define rep(i,n) for (int i=0;i<n;++i)

#define int long long

int n,mx;

std::vector <int> v[Maxn];

int dp[Maxn];

void dfs(int k,int p=-1)

{

	int s=0;

	int ss=0;

	std::vector <int> t;

	for (auto &x:v[k])

	{

		if (x==p)

		{

			continue;

		}

		ss++;

		t.push_back(x);

		dfs(x,k);

		if (dp[x])

		{

			s++;

		}

		dp[k]+=dp[x];

	}

	dp[k]+=std::max(ss-s-1,0ll);

}

signed main()

{

	std::cin>>n;

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

	{

		int x,y;

		std::cin>>x>>y;

		v[x].push_back(y);

		v[y].push_back(x);

	}

	rep(i,n)

	{

		if (v[i].size()>v[mx].size())

		{

			mx=i;

		}

	}

	dfs(mx);

	std::cout<<std::max(1ll,dp[mx])<<std::endl;

	return 0;

}


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

#define maxl 100010



using namespace std;



int n,ans,cnt;

int ehead[maxl];

int du[maxl];

struct ed

{

	int to,nxt;

}e[maxl<<1];

bool vis[maxl];



inline void add(int u,int v)

{

	e[++cnt].to=v;e[cnt].nxt=ehead[u];ehead[u]=cnt;

}



inline void prework()

{

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

		vis[i]=false,ehead[i]=0,du[i]=0;

	int u,v;

	cnt=0;

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

	{

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

		u++;v++;

		add(u,v);du[v]++;

		add(v,u);du[u]++;

	}

}



inline int dfs(int u,int fa)

{

	int v;

	for(int i=ehead[u];i;i=e[i].nxt)

	{

		v=e[i].to;

		if(v==fa) continue;

		if(du[v]>2)

			return v;

		else

			return dfs(v,u);

	}

}



inline void mainwork()

{

	bool flag=true;

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

	if(du[i]>2)

		flag=false;

	if(flag)

	{

		ans=1;

		return;

	}

	ans=0;

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

	if(du[i]==1)

		vis[dfs(i,0)]=true,ans++;

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

	if(vis[i])

		ans--;

}



inline void print()

{

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

}



int main()

{

	while(~scanf("%d",&n))

	{

		prework();

		mainwork();

		print();

	}

	return 0;

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

using namespace std;

const int maxn = 1e5+100;

typedef long long LL;

int val[maxn],First[maxn],cnt,N,M,deg[maxn];

int tot,pre[maxn],rdeg[maxn];

int ans = 0;

struct node{

    int to,Next;

}Tree[maxn*2];

void init(){

    memset(First,-1,sizeof(First));

    cnt = 0;

}

void addedge(int from,int to){

    Tree[cnt].to = to;

    Tree[cnt].Next = First[from];

    First[from] = cnt++;

}

int dfs(int u,int fa){

    if(deg[u]==0)return 0;

    int shoud = deg[u] - 1;

    int bouns = 0;

    for(int i = First[u];i!=-1;i=Tree[i].Next){

        int to = Tree[i].to;

        if(to==fa)continue;

        deg[to]--;

        bouns+=dfs(to,u);

    }

    ans+=max(0,shoud-bouns);

    return bouns||(shoud-bouns);

}

int main(){

    init();

    scanf("%d",&N);

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

        int a,b;

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

        addedge(a,b);

        addedge(b,a);

        deg[a]++;

        deg[b]++;

    }

    int now = 0,max1 = 0;

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

            rdeg[i] = deg[i];

            if(deg[i]>max1){

                now = i;

                max1 = deg[i];

            }

    }

    dfs(now,-1);

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

    return 0;

}

/*

7

0 1

0 2

1 3

1 4

1 5

2 6



*/


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

#define maxl 100010



using namespace std;



int n,ans,cnt;

int ehead[maxl];

int du[maxl];

struct ed

{

	int to,nxt;

}e[maxl<<1];

bool vis[maxl];



inline void add(int u,int v)

{

	e[++cnt].to=v;e[cnt].nxt=ehead[u];ehead[u]=cnt;

}



inline void prework()

{

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

		vis[i]=false,ehead[i]=0,du[i]=0;

	int u,v;

	cnt=0;

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

	{

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

		u++;v++;

		add(u,v);du[v]++;

		add(v,u);du[u]++;

	}

}



inline int dfs(int u,int fa)

{

	int v;

	for(int i=ehead[u];i;i=e[i].nxt)

	{

		v=e[i].to;

		if(v==fa) continue;

		if(du[v]>2)

			return v;

		else

			return dfs(v,u);

	}

}



inline void mainwork()

{

	bool flag=true;

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

	if(du[i]>2)

		flag=false;

	if(flag)

	{

		ans=1;

		return;

	}

	ans=0;

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

	if(du[i]==1)

		vis[dfs(i,0)]=true,ans++;

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

	if(vis[i])

		ans--;

}



inline void print()

{

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

}



int main()

{

	while(~scanf("%d",&n))

	{

		prework();

		mainwork();

		print();

	}

	return 0;

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

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

#define SF scanf

#define PF printf

#define MAXN 100010

using namespace std;

vector<int> a[MAXN];

int n,root=-1;

int dfs(int x,int fa){

    int res=0;

    int flag=0;

    for(int i=0;i<a[x].size();i++){

        if(a[x][i]==fa)

            continue;

        int res1=dfs(a[x][i],x);

        if(res1==0&&flag==1)

            res++;

        if(res1==0&&flag==0)

            flag=1;

        res+=res1;

    }

    return res;

}

int main(){

    SF("%d",&n);

    int u,v;

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

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

        a[u].push_back(v);

        a[v].push_back(u);

    }

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

        if(a[i].size()>=3){

            root=i;

            break;

        }

    if(root==-1){

        PF("1");

        return 0;

    }

    PF("%d",dfs(root,-1));

}

// Faster C++ solution for the same problem (measured speedup: 3.511265385896075x):
/*#pragma comment(linker, "/stack:200000000")

#pragma GCC optimize("Ofast")

#pragma target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/

#include<bits/stdc++.h>

#define ll long long

#define inf 1000000005

#define mod 1000000007

#define put putchar('\n')

#define F(i,a,b) for (int i=(a);i<=(b);i++)

#define D(i,a,b) for (int i=(a);i>=(b);i--)

#define go(i,t) for (int i=head[t];i;i=Next[i])

#define sqr(x) ((x)*(x))

#define re register

#define mp make_pair

#define fi first

#define se second

#define pa pair<int,int>

#define pb push_back

#define be begin()

#define en end()

#define ret return puts("-1"),0;

#define N 500055

//#define int ll

using namespace std;

inline char gc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

#define gc getchar

inline int read(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();}

int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;}

inline void wr(int x){if (x<0) {putchar('-');wr(-x);return;}if(x>=10)wr(x/10);putchar(x%10+'0');}

inline void wrn(int x){wr(x);put;}inline void wri(int x){wr(x);putchar(' ');}

inline void wrn(int x,int y){wri(x);wrn(y);}inline void wrn(int a,int b,int c){wri(a);wrn(b,c);}

int n,m,fa[N],in1[N],ans,x,y;

int nedge,head[N*2],to[N*2],Next[N*2];

#define V to[i]

void add(int a,int b){

   Next[++nedge]=head[a];head[a]=nedge;to[nedge]=b;

}

int dfs(int x,int fa){

	int flag=0,p=0,sum=0;

	go(i,x){

		if (fa==V) continue;

		p=dfs(V,x);

		if (p==0&&flag==1) sum++;

		if (p==0&&flag==0) flag=1;

		sum+=p;

	}

	return sum;

} 

signed main(){

	n=read();

	F(i,1,n-1){

		x=read();y=read();

		add(x,y);add(y,x);in1[x]++;in1[y]++;

	}

	int pd=0;

	F(i,0,n-1){

		if (in1[i]>=3){

			ans=dfs(i,-1);pd=1;

			break;

		} 

	}

	if (!pd){

		wrn(1);return 0;

	}

//	ans=max(ans,1);

	wrn(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.5615120256369326x):
#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;

}
// 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.544127962674094x):
#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;

}
// 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.5892903263479297x):
#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;

}
// 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: 18.750110152470054x):
#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:
/************************************************************************/

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

/****                          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: 18.658589165567754x):
#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]);

}