持续创作，加速成长！这是我参与「日新计划 10 月更文应战」的第32天，点击检查活动详情

标题链接

Problem – A – Codeforces

标题

Through time passes, there is always someone we will never forget.

“Although there were millions of trees in the world, there was only one that The Little Prince took care of with his heart. And although there are countless people in the world, there is only one that I take care of with my heart.” said Zayin to Ziyin with affection.

“Millions of trees? I may not agree with you. Just a tree could have millions of structure.” answered Ziyin proudly, “Let’s do the some math.”

…

Thinking of the days they have happily spent together, Zayin can’t help bursting into tears. Though Ziyin has been gone for a long time, Zayin still misses her every much.

He remembers it was a sunny afternoon when Ziyin and him were lying in the yard, resting beneath the shade of a tree, working on the number of nodes satisfying that if the tree is rooted by the node, the rooted tree is a rooted binary tree.

When times smoothes all sorrows, Zayin also forgets the answer of the problem. He only remember the structure of the tree. Maybe it’s time for Zayin to let all memories about Ziyin go, but he still want to figure out the answer out of sentiment.

As Zayin’s friend, you may want Zayin to get released as soon as possible, can you help him?

In short, given an unrooted tree, please calaculate how many nodes satisfying that if the tree is rooted by the node, the rooted tree is a rooted binary tree.

标题粗心

关于给定的具有 $n$ 个节点的无根树，核算有多少个节点可以作为根节点，使得把整棵树相应拎起来之后构成的有根树是二叉树。

思路

我们先计算每个节点的度，即关于每个节点 $i$，计算与节点 $i$ 相连的边的数量，记为 did_idi​。
假如一个节点作为根节点，则其有 did_idi​ 个子节点，树中的其他节点有 di−1d_i-1di​−1 个子节点（因为有一个边连接了它和它的父节点）。

所以假如整棵树中存在一个节点有大于 3 条边，则不管它作为根节点仍是其他节点，均不能有不超越 2 个子节点，所以合法计划数为 0。不然，所有 di≤2d_i\le 2di​≤2 的节点均可以作为合法的根节点，计算 di≤2d_i\le 2di​≤2 的节点的数量并输出即可。

代码

#include <stdio.h>
using namespace std;
int d[1000001];
int main()
{
	int n;
	scanf("%d",&n);
	for (int i=1;i<n;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		d[x]++;
		d[y]++;
	}
	int flag=1;
	for (int i=1;i<=n;++i)
	{
		if (d[i]>3) flag=0;
	}
	if (!flag)
	{
		printf("0\n");
		return 0;
	}
	int ans=0;
	for (int i=1;i<=n;++i)
	{
		if (d[i]<=2) ans++;
	}
	printf("%d\n",ans);
	return 0;
}