stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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],start;

vii v[100005],tmp;

void dfs(int now,int par){

	int ret=0,c=0;

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

		int to=v[now][i];

		if(to==par) continue;

		dfs(to,now);

	}

	tmp.clear();

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

		int to=v[now][i];

		if(to==par) continue;

		if(!dp[to]) c++;

		else ret+=dp[to];

	}

	ret+=max(0,c-1);

	dp[now]=ret;

}

int mx=0;

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);

	}

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

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

			mx=v[i].size();

			start=i;

		}

	}

	if(mx<=2){

		puts("1");

		return 0;

	}

	dfs(start,-1);

//	for(int i=0;i<n;i++) cout<<dp[i]<<' ';cout<<'\n';

	cout<<dp[start]<<'\n';

	return 0;

}

/*

17

0 1

0 2

0 3

1 4

1 5

4 10

4 11

2 6

6 12

6 13

3 7

3 8

3 9

8 16

16 14

16 15

*/

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

using namespace std;



const int maxn=100010;

int du[maxn];

int n,root;

struct Edge

{

	int v,next;

}	e[maxn<<1];

int g[maxn],tot;

int fa[maxn];

bool has[maxn];

int ans;

void addedge(int x,int y)

{

	tot++;

	e[tot].v=y;

	e[tot].next=g[x];

	g[x]=tot;

}

void dfs(int t)

{

	int son=du[t];

	if (fa[t]!=0)	son--;

	for (int i=g[t];i;i=e[i].next)

	if (e[i].v!=fa[t])

	{

		fa[e[i].v]=t;

		dfs(e[i].v);

		if (has[e[i].v])	son--,has[t]=true;

	}

	if (son>1)

	{

		ans+=son-1;

		has[t]=true;

	}

}

int main()

{

	scanf("%d",&n);

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

	{

		int x,y;

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

		x++;y++;

		addedge(x,y);

		addedge(y,x);

		du[x]++;

		du[y]++;

		if (du[x]>2)	root=x;

	}

	if (!root)

	{

		printf("1\n");

		return 0;

	}

	ans=0;

	fa[root]=0;

	dfs(root);

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

	return 0;

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

using namespace std;

const int boss=1e5;

int n,m,vis[boss+10];

vector<int> lj[boss+10];

int dfs(int u,int fa)

{

if (lj[u].size()>2) return u;

for (int i:lj[u]) if (i!=fa) return dfs(i,u);

return u;

}

int main()

{

int i,u,v;

scanf("%d",&n);

for (i=1;i<n;i++) scanf("%d%d",&u,&v),u++,v++,lj[u].push_back(v),lj[v].push_back(u);

for (i=1;i<=n;i++) if (lj[i].size()==1) vis[dfs(i,0)]=1,m++;

for (i=1;i<=n;i++) if (vis[i]) m--;

printf("%d",max(m,1));

}

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

using namespace std;



const int maxn=100010;

int du[maxn];

int n,root;

struct Edge

{

	int v,next;

}	e[maxn<<1];

int g[maxn],tot;

int fa[maxn];

bool has[maxn];

int ans;

void addedge(int x,int y)

{

	tot++;

	e[tot].v=y;

	e[tot].next=g[x];

	g[x]=tot;

}

void dfs(int t)

{

	int son=du[t];

	if (fa[t]!=0)	son--;

	for (int i=g[t];i;i=e[i].next)

	if (e[i].v!=fa[t])

	{

		fa[e[i].v]=t;

		dfs(e[i].v);

		if (has[e[i].v])	son--,has[t]=true;

	}

	if (son>1)

	{

		ans+=son-1;

		has[t]=true;

	}

}

int main()

{

	scanf("%d",&n);

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

	{

		int x,y;

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

		x++;y++;

		addedge(x,y);

		addedge(y,x);

		du[x]++;

		du[y]++;

		if (du[x]>2)	root=x;

	}

	if (!root)

	{

		printf("1\n");

		return 0;

	}

	ans=0;

	fa[root]=0;

	dfs(root);

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

	return 0;

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

using namespace std;

int dp[100005], n;

vector<int> c[100005];

void dfs(int x, int pa){

	int add = 0;

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

		int v = c[x][i];

		if(v != pa){

			dfs(v, x);

			dp[x] += dp[v];

			if(dp[v] == 0) add++;

		}

	}

	dp[x] += max(add - 1, 0);

}

int main(){

	cin >> n;

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

		int x, y;

		cin >> x >> y;

		c[x].push_back(y);

		c[y].push_back(x);

	}

	int maxi = 0;

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

		if(c[i].size() > c[maxi].size()) maxi = i;

	}

	if(c[maxi].size() < 2){

		cout << 1;

		return 0;

	}

	dfs(maxi, -1);

	cout << dp[maxi] << endl;

}

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

using namespace std;



const int MAXN = 101010;



int n, m;



int ind[MAXN];



class Road {

public:

	int t, next;

}e[MAXN * 2];

int p[MAXN];

int z = -1;



int vis[MAXN];



void add(int u, int v) {

	++z;

	e[z].t = v;

	e[z].next = p[u];

	p[u] = z;

}



int cnt = 0;



bool dfs(int u, int fa) {

	//cout<<u<<" "<<fa<<endl;

	int cnt1 = 0, cnt2 = 0;

	for(int tmp = p[u]; tmp != -1; tmp = e[tmp].next) {

		if(e[tmp].t != fa) {

			cnt1++;

			cnt2 += dfs(e[tmp].t, u);

		}

	}

	if(cnt1 - 1 > cnt2) {

		cnt += cnt1 - 1 - cnt2;

		return true;

	}

	return cnt2;

}



int main() {

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

	

	scanf("%d", &n);

	int u, v;

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

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

		ind[u]++, ind[v]++;

		add(u, v);

		add(v, u);

	}

	int mx = 0, mxp;

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

		if(ind[i] > mx) {

			mx = ind[i];

			mxp = i;

		}

	if(mx <= 2) {

		puts("1");

		return 0;

	}

	dfs(mxp, -1);

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



	return 0;

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

using namespace std;

const int boss=1e5;

int n,m,vis[boss+10];

vector<int> lj[boss+10];

int dfs(int u,int fa)

{

if (lj[u].size()>2) return u;

for (int i:lj[u]) if (i!=fa) return dfs(i,u);

return u;

}

int main()

{

int i,u,v;

scanf("%d",&n);

for (i=1;i<n;i++) scanf("%d%d",&u,&v),u++,v++,lj[u].push_back(v),lj[v].push_back(u);

for (i=1;i<=n;i++) if (lj[i].size()==1) vis[dfs(i,0)]=1,m++;

for (i=1;i<=n;i++) if (vis[i]) m--;

printf("%d",max(m,1));

}

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

using namespace std;



const int MAXN = 101010;



int n, m;



int ind[MAXN];



class Road {

public:

	int t, next;

}e[MAXN * 2];

int p[MAXN];

int z = -1;



int vis[MAXN];



void add(int u, int v) {

	++z;

	e[z].t = v;

	e[z].next = p[u];

	p[u] = z;

}



int cnt = 0;



bool dfs(int u, int fa) {

	//cout<<u<<" "<<fa<<endl;

	int cnt1 = 0, cnt2 = 0;

	for(int tmp = p[u]; tmp != -1; tmp = e[tmp].next) {

		if(e[tmp].t != fa) {

			cnt1++;

			cnt2 += dfs(e[tmp].t, u);

		}

	}

	if(cnt1 - 1 > cnt2) {

		cnt += cnt1 - 1 - cnt2;

		return true;

	}

	return cnt2;

}



int main() {

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

	

	scanf("%d", &n);

	int u, v;

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

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

		ind[u]++, ind[v]++;

		add(u, v);

		add(v, u);

	}

	int mx = 0, mxp;

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

		if(ind[i] > mx) {

			mx = ind[i];

			mxp = i;

		}

	if(mx <= 2) {

		puts("1");

		return 0;

	}

	dfs(mxp, -1);

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



	return 0;

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

using namespace std;

int dp[100005], n;

vector<int> c[100005];

void dfs(int x, int pa){

	int add = 0;

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

		int v = c[x][i];

		if(v != pa){

			dfs(v, x);

			dp[x] += dp[v];

			if(dp[v] == 0) add++;

		}

	}

	dp[x] += max(add - 1, 0);

}

int main(){

	cin >> n;

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

		int x, y;

		cin >> x >> y;

		c[x].push_back(y);

		c[y].push_back(x);

	}

	int maxi = 0;

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

		if(c[i].size() > c[maxi].size()) maxi = i;

	}

	if(c[maxi].size() < 2){

		cout << 1;

		return 0;

	}

	dfs(maxi, -1);

	cout << dp[maxi] << endl;

}

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

#include<cstdio>

const int N=1e5+5;

int n,cnt,head[N],nxt[N<<1],to[N<<1],deg[N];

void init() {

    for(int i=0;i<n;i++) head[i]=-1,deg[i]=0;cnt=0;

}

void addEdge(int u,int v) {

    nxt[cnt]=head[u];to[cnt]=v;head[u]=cnt++;

}

int dfs(int u,int fa) {

    int ans=0;bool f=false;

    for(int i=head[u];~i;i=nxt[i]) {

        int v=to[i];if(v==fa) continue;

        int tmp=dfs(v,u);

        ans+=tmp?tmp:f;

        f=f||!tmp;

    }

    return ans;

}

int main() {

    scanf("%d",&n);init();int u,v;

    for(int i=1;i<n;i++) scanf("%d%d",&u,&v),addEdge(u,v),addEdge(v,u),deg[v]++,deg[u]++;

    int root=-1;

    for(int i=0;i<n;i++) if(deg[i]>2) root=i;

    printf("%d\n",root==-1?1:dfs(root,-1));

    return 0;

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

using namespace std;

const int boss=1e5;

int n,m,vis[boss+10];

vector<int> lj[boss+10];

int dfs(int u,int fa)

{

if (lj[u].size()>2) return u;

for (int i:lj[u]) if (i!=fa) return dfs(i,u);

return u;

}

int main()

{

int i,u,v;

scanf("%d",&n);

for (i=1;i<n;i++) scanf("%d%d",&u,&v),u++,v++,lj[u].push_back(v),lj[v].push_back(u);

for (i=1;i<=n;i++) if (lj[i].size()==1) vis[dfs(i,0)]=1,m++;

for (i=1;i<=n;i++) if (vis[i]) m--;

printf("%d",max(m,1));

}

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

#include<cstdio>

const int N=1e5+5;

int n,cnt,head[N],nxt[N<<1],to[N<<1],deg[N];

void init() {

    for(int i=0;i<n;i++) head[i]=-1,deg[i]=0;cnt=0;

}

void addEdge(int u,int v) {

    nxt[cnt]=head[u];to[cnt]=v;head[u]=cnt++;

}

int dfs(int u,int fa) {

    int ans=0;bool f=false;

    for(int i=head[u];~i;i=nxt[i]) {

        int v=to[i];if(v==fa) continue;

        int tmp=dfs(v,u);

        ans+=tmp?tmp:f;

        f=f||!tmp;

    }

    return ans;

}

int main() {

    scanf("%d",&n);init();int u,v;

    for(int i=1;i<n;i++) scanf("%d%d",&u,&v),addEdge(u,v),addEdge(v,u),deg[v]++,deg[u]++;

    int root=-1;

    for(int i=0;i<n;i++) if(deg[i]>2) root=i;

    printf("%d\n",root==-1?1:dfs(root,-1));

    return 0;

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

using namespace std;



const int MAXN = 101010;



int n, m;



int ind[MAXN];



class Road {

public:

	int t, next;

}e[MAXN * 2];

int p[MAXN];

int z = -1;



int vis[MAXN];



void add(int u, int v) {

	++z;

	e[z].t = v;

	e[z].next = p[u];

	p[u] = z;

}



int cnt = 0;



bool dfs(int u, int fa) {

	//cout<<u<<" "<<fa<<endl;

	int cnt1 = 0, cnt2 = 0;

	for(int tmp = p[u]; tmp != -1; tmp = e[tmp].next) {

		if(e[tmp].t != fa) {

			cnt1++;

			cnt2 += dfs(e[tmp].t, u);

		}

	}

	if(cnt1 - 1 > cnt2) {

		cnt += cnt1 - 1 - cnt2;

		return true;

	}

	return cnt2;

}



int main() {

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

	

	scanf("%d", &n);

	int u, v;

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

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

		ind[u]++, ind[v]++;

		add(u, v);

		add(v, u);

	}

	int mx = 0, mxp;

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

		if(ind[i] > mx) {

			mx = ind[i];

			mxp = i;

		}

	if(mx <= 2) {

		puts("1");

		return 0;

	}

	dfs(mxp, -1);

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



	return 0;

}

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

#include<cstdio>

const int N=1e5+5;

int n,cnt,head[N],nxt[N<<1],to[N<<1],deg[N];

void init() {

    for(int i=0;i<n;i++) head[i]=-1,deg[i]=0;cnt=0;

}

void addEdge(int u,int v) {

    nxt[cnt]=head[u];to[cnt]=v;head[u]=cnt++;

}

int dfs(int u,int fa) {

    int ans=0;bool f=false;

    for(int i=head[u];~i;i=nxt[i]) {

        int v=to[i];if(v==fa) continue;

        int tmp=dfs(v,u);

        ans+=tmp?tmp:f;

        f=f||!tmp;

    }

    return ans;

}

int main() {

    scanf("%d",&n);init();int u,v;

    for(int i=1;i<n;i++) scanf("%d%d",&u,&v),addEdge(u,v),addEdge(v,u),deg[v]++,deg[u]++;

    int root=-1;

    for(int i=0;i<n;i++) if(deg[i]>2) root=i;

    printf("%d\n",root==-1?1:dfs(root,-1));

    return 0;

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

#include <cstdlib>

#include <algorithm>

#include <vector>



const int maxn = 1e5 + 20;



int n, m;

std::vector<int> G[maxn];

bool vis[maxn];



int dfs(int u,int fa)

{

	if(G[u].size() > 2) return u;

	

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

	{

		int v = G[u][i];

		

		if(v != fa) return dfs(v, u);

	}

	

	return u;

}

int main()

{

	scanf("%d", &n);

	for(int i = 1, u, v; i < n; i++)

	{

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

		u++, v++;

		G[u].push_back(v);

		G[v].push_back(u);

	}

	

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

		if(G[i].size() == 1) vis[dfs(i, 0)] = true, m++;

	

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

		if(vis[i]) m--;

	

	m = std::max(m, 1);

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

	return 0;

}

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

#include<cstdio>

const int N=1e5+5;

int n,cnt,head[N],nxt[N<<1],to[N<<1],deg[N];

void init() {

    for(int i=0;i<n;i++) head[i]=-1,deg[i]=0;cnt=0;

}

void addEdge(int u,int v) {

    nxt[cnt]=head[u];to[cnt]=v;head[u]=cnt++;

}

int dfs(int u,int fa) {

    int ans=0;bool f=false;

    for(int i=head[u];~i;i=nxt[i]) {

        int v=to[i];if(v==fa) continue;

        int tmp=dfs(v,u);

        ans+=tmp?tmp:f;

        f=f||!tmp;

    }

    return ans;

}

int main() {

    scanf("%d",&n);init();int u,v;

    for(int i=1;i<n;i++) scanf("%d%d",&u,&v),addEdge(u,v),addEdge(v,u),deg[v]++,deg[u]++;

    int root=-1;

    for(int i=0;i<n;i++) if(deg[i]>2) root=i;

    printf("%d\n",root==-1?1:dfs(root,-1));

    return 0;

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

#include<vector>

#include<algorithm>

#define MAXN 200006

using namespace std;

int d[MAXN],n,a,b;

vector<int> road[MAXN];

void DFS(int x,int fa)

{

	int ok=0;

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

	{

		int nex=road[x][i];

		if(nex==fa) continue;

		DFS(nex,x);

		if(d[nex]==0)

		{

			if(ok==0) ok=1;

			else d[x]++;

		}

		else d[x]+=d[nex];

	}

}

int main()

{

	scanf("%d",&n);

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

	{

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

		a++;

		b++;

		road[a].push_back(b);

		road[b].push_back(a);

	}

	int st=0;

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

	{

		if(road[i].size()>=3)

		{

			st=i;

			break;

		}

	}

	if(st==0) printf("1");

	else 

	{

		DFS(st,0);

		printf("%d",d[st]);

	}

}

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

#include<cstdio>

const int N=1e5+5;

int n,cnt,head[N],nxt[N<<1],to[N<<1],deg[N];

void init() {

    for(int i=0;i<n;i++) head[i]=-1,deg[i]=0;cnt=0;

}

void addEdge(int u,int v) {

    nxt[cnt]=head[u];to[cnt]=v;head[u]=cnt++;

}

int dfs(int u,int fa) {

    int ans=0;bool f=false;

    for(int i=head[u];~i;i=nxt[i]) {

        int v=to[i];if(v==fa) continue;

        int tmp=dfs(v,u);

        ans+=tmp?tmp:f;

        f=f||!tmp;

    }

    return ans;

}

int main() {

    scanf("%d",&n);init();int u,v;

    for(int i=1;i<n;i++) scanf("%d%d",&u,&v),addEdge(u,v),addEdge(v,u),deg[v]++,deg[u]++;

    int root=-1;

    for(int i=0;i<n;i++) if(deg[i]>2) root=i;

    printf("%d\n",root==-1?1:dfs(root,-1));

    return 0;

}
// 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: 18.741240919509675x):
#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:
//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: 18.766244294472795x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 100000

struct node

{

	int to;

	node *next;

}edge[MAXN*2+5];

node *ncnt=&edge[0],*Adj[MAXN+5];

int d[MAXN+5],root=MAXN+5,dp[MAXN+5];

bool vis[MAXN+5];

int n;

void AddEdge(int u,int v)

{

	node *p=++ncnt;

	p->to=v;

	p->next=Adj[u];

	Adj[u]=p;

	

	node *q=++ncnt;

	q->to=u;

	q->next=Adj[v];

	Adj[v]=q;

}

void dfs(int u)

{

	vis[u]=true;

	int chnum=0,nothave=0;

	for(node *p=Adj[u];p!=NULL;p=p->next)

	{

		int v=p->to;

		if(vis[v]==false)

		{

			chnum++;

			dfs(v);

			dp[u]+=dp[v];

			if(dp[v]==0)

				nothave++;

		}

	}

	if(nothave>=2)

		dp[u]+=nothave-1;

}

int main()

{

	scanf("%d",&n);

	int x,y;

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

	{

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

		AddEdge(x,y);

		d[x]++,d[y]++;

	}

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

	{

		if(d[i]>=3)

		{

			root=i;

			break;

		}

	}

	if(root>MAXN)

	{

		printf("1\n");

		return 0;

	}

	dfs(root);

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

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



*/