題目傳送門 - UOJ#23題意
給定一個有 n 個節點的仙人掌（可能有重邊）。
對于所有的 $L(1\leq L\leq n-1)$ ，求出有多少不同的從節點 1 出發的包含 L 條邊的簡單路徑。簡單路徑是指不重複經過任意一點。
$n\leq 10^5$
題解
首先我們把走一條邊看作多項式 $x^1$ ，那麼一條長度為 L 的路徑就是其路徑上的多項式的乘積。
接下來稱“環根”為距離節點 1 最近的那個節點。
假設 $p_v$ 為點 v 對最終答案的貢獻，那麼 $p_v$ 是什麼？分兩種情況讨論：
1. v 屬于某個環且 v 不是該環的環根。那麼顯然這個環的環根（設為 u）更靠近 1 ，假設 v 到 u 的兩條路徑長度分别是 a 和 b ，那麼 $p_v=p_u \times (x^a+x^b)$ 。
2. 假設有一個點 u 不和 v 在同一個環中，且 u 距離 1 比 v 距離 1 更近，那麼 $p_v=p_u\times x$ 。
于是到此為止我們已經可以輕松的解決 50 分了。
然而跳蚤國的疆域着實太大……
考慮對于仙人掌進行點分治，然後對于目前連通塊 $T$ ，我們找點分中心 $x$ 。
怎麼找點分中心？——類比找樹的點分中心，"找一個結點，把和它相連的邊都斷了并且他在的每一個環上的邊都要去掉（不去掉環上的其它結點）。這樣找出連通塊最大的最小作為重心。"
定義連通塊的根為目前連通塊中在原圖距離 1 最近的點。
于是我們可以分治 FFT 求出點分中心 x 到 目前連通塊的根 的多項式。
結合點分治，總複雜度為 $O(n\log^3 n)$ ，可能可以通過此題。
——VFleaKing
UOJ#23. 【UR #1】跳蚤國王下江南 仙人掌 Tarjan 點雙 圓方樹 點分治 多項式 FFT
對于目前點分中心 x ，如果我們先将比 x 靠近連通塊根的那個子仙人掌處理了，那麼，我們會發現我們在這時要算的多項式大部分已經算好了。這裡隻需要做的就是合并。可以發現，從 x 追根溯源得到的這些多項式有 $O(\log n)$ 個，而且他們的最高次項指數是和對應的連通塊的 size 相關的，又由于對于這些連通塊，我們做的是點分治，是以這些多項式的最高次項指數是大約 2 倍兩倍增長的。是以現在求點分中心 x 到 目前連通塊的根 的多項式，隻需要 $T(n) = T(n/2) + O(n\log n) = O(n\log n)$ 的時間複雜度。
結合點分治，我們可以得到一個 $O(n\log ^2 n)$ 的優秀做法。
當然，底層實作的時候還是有一些細節需要注意，這裡就不展開贅述了(饒了我吧，懶得寫了……)。
由于部落客人傻常數大，是以用時差點吃雞了。
順便贈送樣例 2 的圖，以及其圓方樹。
代碼