ZUFEOJ
Home
ProblemSet
Source/Category
Contest
Status
Ranklist
F.A.Qs
ContestProblemSetList
Login
Register
问题 A: 造花(简单版)
内存限制:256 MB
时间限制:6 S
题面:Markdown
评测方式:文本比较
上传者:
提交:21
通过:6
返回比赛
提交
提交记录
题目描述
给定一棵 $n$ 个点的树,请选择并删除这棵树上的一个点和连向这个点的所有边,使得整个图只剩下[b]恰好两个[/b]连通块,且每个连通块都构成菊花图,请问这是否可以做到。 一个 $n$ 个点的连通图是菊花图,当且仅当它是一棵树,且至少有一个点与其它 $n-1$ 个点之间都有边直接相连。特别地,一个点的树也是菊花图。
输入格式
第一行一个整数 $T$($1\le T\le 10^5$),表示测试数据组数。 每组数据第一行一个整数 $n$($3\le n\le 2\times 10^5$),表示树的节点个数。 接下来 $n-1$ 行描述了一棵树,每行两个整数 $u$ 和 $v$($1\le u,v\le n$),表示树上的一条边。 数据保证 $\sum n \le 2\times 10^6$。
输出格式
对于每组数据输出一行,如果可以通过删点操作使得整个图变成两个菊花图,输出 $\texttt{Yes}$,否则输出 $\texttt{No}$。
输入样例
复制
3 3 1 2 2 3 4 1 2 1 3 1 4 7 1 2 1 3 2 4 2 5 3 6 3 7
输出样例
复制
Yes No Yes
数据范围与提示
由于本题读入量较大,推荐使用 $\texttt{fread}$ 函数进行数据读入。
分类标签
2024杭电多校第六场