Description

有一個(gè)樹形結(jié)構(gòu)的賓館，n個(gè)房間，n-1條無向邊，每條邊的長度相同，任意兩個(gè)房間可以相互到達(dá)。吉麗要給他的三個(gè)妹子各開（一個(gè)）房（間）。三個(gè)妹子住的房間要互不相同（否則要打起來了），為了讓吉麗滿意，你需要讓三個(gè)房間兩兩距離相同。
有多少種方案能讓吉麗滿意？

Input

第一行一個(gè)數(shù)n。
接下來n-1行，每行兩個(gè)數(shù)x,y，表示x和y之間有一條邊相連。

Output

讓吉麗滿意的方案數(shù)。

Sample Input

7
1 2
5 7
2 5
2 3
5 6
4 5

Sample Output

5

HINT

【樣例解釋】
{1,3,5},{2,4,6},{2,4,7},{2,6,7},{4,6,7}

【數(shù)據(jù)范圍】
n≤5000

?

因?yàn)槊績牲c(diǎn)路徑是唯一的，所以這三個(gè)房間一定存在一個(gè)中心，中心到三個(gè)房間距離相等。

直接枚舉中心然后對于每顆子樹dfs算出以這個(gè)點(diǎn)為中心的方案數(shù)。

權(quán)限號又不行了，沒法交題，難過。

轉(zhuǎn)載于:https://www.cnblogs.com/Serene-shixinyi/p/7581019.html

總結(jié)

以上是生活随笔為你收集整理的bzoj3522 Hotel的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。