a668. E. Triple-Tree - 旦旦解題農場

內容

地球上有許多種類的樹，像是榕樹、樟樹等等。而其中有許多樹隨著人類的發展也逐漸地面臨絕種，其中主要的威脅有清除林地轉供農地、畜牧使用，伐木業，氣候變遷等等。這些都是造成絕種的原因之一。而其中有一種樹叫做 Triple-Tree ，他是一種稀有的樹，而如果要分辨一棵樹是不是Triple-Tree 的話，則可以將樹上的點分成剛好三個三個一組，每個節點只屬於其中一組，如果三個節點彼此距離 (距離為兩點間邊的數量) 相差 $\le 2$，則他們可以為同一組

給你一棵 $N$ 個點的樹，想問你他是不是一棵 Triple-Tree ?

( 其中一棵 Triple-Tree )

輸入說明

第一行有一個整數 $T(1 \le T \le 10^5)$ ，代表接下來有 $T$ 筆測資

每筆測資第一行有一個整數 $N (1 \le N \le 2 \cdot 10^5)$ ，代表有$N$個節點

接下來有 $N-1$ 行，每行有兩個整數 $u , v (1 \le u,v \le n，u \neq v)$，

代表點 $u$ 與點 $v$ 之間有連邊

- subtask 1 : 保證最多只有一點連超過兩條邊 $(27\%)$
- subtask 2 : 無其他特殊限制 $(73\%)$

保證所有 $N$ 加起來不超過 $10^6$

輸出說明

對於每筆測資，如果為 Triple-Tree 輸出 $YES$ ，否則輸出 $NO$

範例輸入

範例輸出

YES
NO

測資資訊：

記憶體限制： 64 MB
不公開測資點#0 (26%): 1.0s , <1M
不公開測資點#1 (1%): 1.0s , <10M
不公開測資點#2 (66%): 1.0s , <10M
不公開測資點#3 (1%): 1.0s , <50M
不公開測資點#4 (1%): 1.0s , <50M
不公開測資點#5 (1%): 1.0s , <50M
不公開測資點#6 (1%): 1.0s , <10M
不公開測資點#7 (1%): 1.0s , <10M
不公開測資點#8 (1%): 1.0s , <10M
不公開測資點#9 (1%): 1.0s , <10M

提示：

標籤:

出處:

110學年度FD校內資訊學科能力競賽(一) [管理者：

fdhs105285 (jakao)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」