題意

給一棵樹，每個點有編號，現在有一種樹 \(f(l,r)\)，形如把編號在 \([l,r]\) 之間的點連成最小生成樹。

然后給一些詢問，形如 \(q(L_i,R_i)\)。他想知道有多少種不同的 \(f(l,r)\)，其中 \(L_i\le l\le r\le R_i\)。

稱 \(f\) 相同，當且僅當其包含的點集相同。

對于所有測試數據，保證：

• \(1\le n,q\le 5\times 10^5\)；
• \(1\le L_i\le R_i\le n\)；
• \(1\le x,y\le n\)，保證輸入的邊構成樹。

題解

考慮每種 \(f(l,r)\) 的性質，必然 \(l\) 不變的情況下 \(r\) 遞增，則 \(f(l,r)\) 的樹是不變小的。有點單調的感覺，所以考慮找到每種樹的分界點 \((l,r)\)。這里有個結論，就是這個 \(l,r\) 一定都是最小生成樹的葉子，證明顯然。

然后考慮每個點作為這種 \(l\) 或者 \(r\) 的最遠擴展距離。這里我們可以這么想：對于 \(l\) 來說，如果把 \(l\) 當成根，那么必須經過 \(l\) 當且僅當 \(l\) 有至少 \(2\) 個子樹有點，所以我們把這個東西放到 \(dfs\) 序上就是區間最大值了，枚舉子樹找到第二大就是答案。從小到大掃描每個點即可，\(r\) 的做法類似。

接下來考慮計算答案，我們設每個點能拓展的左右端點為 \(L_i,R_i\)，詢問區間為 \(l,r\)，我們要找的兩個葉子從小到大為為 \(x,y\)。那么我們要求的點對滿足如下限制：

考慮掃描 \(y\)，用線段樹維護。具體來說線段樹每個節點維護一個值 \(w_i\) 表示以 \(i\) 為左端點，右端點不超過 \(y\) 的樹種類。我們維護一個 \(tag_i=[R_i\ge y]\) 那么一次掃描的增加會使得 \([l_y,y]\) 中的點變為 \(w_i+tag_i\)。發現 \(tag_i\) 只會改變一次，所以可以暴力修改 \(tag_i\)，詢問就是求區間和，線段樹上每個節點維護 \(sumw,sumtag\) 就可以了。