F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

造花(简单版)

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 638    Accepted Submission(s): 194


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

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

Input
第一行一个整数 T1\le T\le 10^5),表示测试数据组数。

每组数据第一行一个整数 n3\le n\le 2\times 10^5),表示树的节点个数。

接下来 n-1 行描述了一棵树,每行两个整数 uv1\le u,v\le n),表示树上的一条边。

数据保证 \sum n \le 2\times 10^6
 

Output
对于每组数据输出一行,如果可以通过删点操作使得整个图变成两个菊花图,输出 \texttt{Yes},否则输出 \texttt{No}
 

Sample Input
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
 

Sample Output
Yes No Yes
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2025 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.001000(s) query 1, Server time : 2025-04-01 09:08:10, Gzip enabled