请登录

4992.造花(简单版)

时间限制:3s 内存限制:256MB

给定一棵 $n$ 个点的树,请选择并删除这棵树上的一个点和连向这个点的所有边,使得整个图只剩下恰好两个连通块,且每个连通块都构成菊花图,请问这是否可以做到。

一个 $n$ 个点的连通图是菊花图,当且仅当它是一棵树,且至少有一个点与其它 $n−1$ 个点之间都有边直接相连。特别地,一个点的树也是菊花图。

输入格式(从终端/标准输入读取)

第一行一个整数 $T(1≤T≤10^5)$,表示测试数据组数。

每组数据第一行一个整数 $n(3≤n≤2×10^5)$,表示树的节点个数。

接下来 $n−1$ 行描述了一棵树,每行两个整数 $u 和 $v(1≤u,v≤n)$,表示树上的一条边。

数据保证 $∑n≤2×10^6$ 。

输出格式(输出至终端/标准输出)

对于每组数据输出一行,如果可以通过删点操作使得整个图变成两个菊花图,输出 $Yes$,否则输出 $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
 \n
 \n
 · \n
 · \n
 \n
 · \n
 · \n
 · \n
 \n
 · \n
 · \n
 · \n
 · \n
 · \n
 · \n

输出样例

复制
Yes
No
Yes
   \n
  \n
   \n

说明

由于本题读入量较大,推荐使用 $fread$ 函数进行数据读入。

来源: 2024“钉耙编程”中国大学生算法设计超级联赛(6)

提交题解

Please login first.

© 2025 FAQs