本地AC 提交WA P1922
查看原帖
本地AC 提交WA P1922
196882
银行密码器楼主2020/8/19 11:28
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+20;
struct data {
	int to,stb;
} a[N];
int head[N],tot,v[N],f[N];
void insert(int x,int y) {
	a[++tot].to=y;
	a[tot].stb=head[x];
	head[x]=tot;
}
void dp(int x,int fa) {
	int num=1;
	for(int i=head[x]; i; i=a[i].stb) {
		int xx=a[i].to;
		if(xx==fa) continue;
		dp(xx,x);
		if(!v[xx]) num++;
		else f[x]+=f[xx];
	}
	f[x]+=num/2;
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n-1; i++) {
		int x,y;
		scanf("%d%d",&x,&y);
		insert(x,y);
		insert(y,x);
		v[x]++;
	}
	dp(1,0);
	printf("%d",f[1]); 
	return 0;
}
2020/8/19 11:28
加载中...