An unavoidable detour for home
題意
有n座城市，城市間可能有無向邊連接靖榕。有以下特點：
- 兩座城市間最多一條邊标锄，不會有邊連接自己。
-
定義第一座城市為首都茁计，每座城市到首都的路徑經(jīng)過的邊數(shù)為距離料皇，那么每座城市必有且只有一條到首都的最短路徑，下稱第i座城市到首都的最短距離為
- 
-
設(shè)第i座城市的度數(shù)為那么有
給定n以及每座城市的度數(shù)星压，求可能的路網(wǎng)數(shù)量(取模)践剂。
題解
如果我們把按照度數(shù)給城市上色，那么看起來可能是這樣的：
image.png
由2可知娜膘，每座城市必定連接編號比自己小的城市逊脯，所以有且，否則i的最短距就要大于i-1的了竣贪，如上圖中城市7只能在4,军洼、5、 6中選一個連接演怎。
如果我們逐個城市逐個城市地加入路網(wǎng)匕争，每個城市必須和前面的城市連一條路，剩下的路可以繼續(xù)和前面的連接(注意最短路徑唯一)爷耀，也可以留著給后來的城市連接甘桑，那么任意時刻，剩余度數(shù)大于0的城市的最短距最多兩種歹叮，且它們的差為1跑杭，且它們是最短距最大的，而題目限定了每個城市的度數(shù)為2或3盗胀，所以剩余度數(shù)有1,2，也就是說锄贼，剩余可連的城市最多只有四種票灰。
到了這一步，結(jié)合n的大小宅荤，看起來是不是很像dp屑迂？dp的轉(zhuǎn)移公式也很明顯了，如果擔(dān)心遍歷50*50*50*50太慢冯键，可以剪枝惹盼。
