列表

详情

NC230907. 火凤燎原

描述

从风暴中归来，在烈火中重生。

「蒲公英」是树上的一个连通子集，有且仅有一个「中心点」，另外：

设「中心点」在原树中的度为 ，则必须有 k-1 个结点在「蒲公英」中是一个单点，剩下一条链；那条链的本身长度（不包含 u）必须不少于 2。（下图中 0 号结点即为「中心点」而它的度为 6）



两个「蒲公英」本质不同，当且仅当中心点 u 不同或对应的链包含的结点不同。（至少存在一个结点 v 属于一个「蒲公英」而不属于另一个「蒲公英」）

给定一棵无根树，求其中「蒲公英」的个数。

输入描述

全文第一行输入数据组数 。

对每组数据，第一行输入一个正整数 ，表示树的结点个数。

第  行输入两个正整数 ，表示一条树边。

输出描述

输出本质不同「蒲公英」的个数。

示例1

输入: 

5
5
1 2
2 3
1 4
1 5
7
1 3
2 3
3 4
3 6
4 5
6 7
9
1 2
1 4
1 5
2 3
2 6
2 7
2 8
2 9
10
1 2
2 3
3 4
4 5
3 6
6 7
3 8
8 9
9 10
20
20 18
1 3
19 12
19 4
16 1
4 1
1 7
16 10
7 20
13 8
10 2
18 13
13 17
14 18
11 19
16 5
2 6
16 9
17 15

输出: 

1
2
7
5
78

说明:

对于样例 #1，整棵树本身就是一个蒲公英。

对于样例 #2 \sim #4，样例解释如下图所示：


原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 429ms, 内存消耗: 784K, 提交时间: 2021-12-17 20:24:29 

#include<iostream>
using namespace std;
int t,n,x,y,cx[200005];
long long ans;
int main(void){
	cin>>t;
	while(t--){
		cin>>n;
		ans=0;
		for( int i=n;i>=1;--i)cx[i]=0;
		for( int i=1;i<=n-1;++i){
			scanf("%d%d",&x,&y);
			cx[x]++;
			cx[y]++;
		}
		for( int i=n;i>=1;--i){
			if(cx[i]>=3){
				ans+=n-1-cx[i];
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

上一题

© 2024 nowcoder.com