T1

很水的計數。

T2

注意到如果滿足分割條件，那么選取的點需要滿足一下要求：

• 所有分割點的深度相同：因為如果不滿足這一點，我們可以進行分類討論：

  • 如果存在深度比其他點小的點，那么它一定是 \(b_1\)，又因為其他點的深度小于它，所以它們包含深度的交集一定包含這個點的深度，故不滿足條件；

  • 如果存在深度比其他點大的點，那么它一定不是 \(b_1\)，又因為它比其它點的深度大，那么 \(b_1\) 的深度一定不屬于交集。

• 這個深度上至少有 \(k+1\) 個點：你需要留一個點給第 \(k+1\) 顆子樹。

那么我們對每一層上的點進行統計：首先，我們可以明確的是，一個點做 \(b_1\) 時，其他點的高度一定要大于等于它。不然交集會小于該點的高度集；且必須有一個點的高度等于它，不然我們也不能使交集等于它的高度集。我們記有 \(x\) 個點的高度大于它，有 \(y\) 個點的高度等于它（包括它自己）。接下來是一個小分討：

• 如果 \(y=1\)：那么沒有答案。

• 如果當前有 \(k-1\) 個點的高度大于它：那么我們此時可以只選一個點作為分割點。所以貢獻為 \(x\times A_{y}^{k-1}\)；

• 如果當前有 \(y \ge 2\)：那么我們可以容斥一下：把任意選取的方案數減去 \(k-1\) 個全選高度大于它的方案數，即 \(x \times(A_{x+y-1}^{k-1}-A_{y}^{k-1})\)。

T3

我們先考慮怎么回答詢問，再考慮怎么修改。

首先，我們抽象一下這個問題：我們想從 \([1,x]\) 中的某一個點到 \([y,n]\)，且使距離最小。

這個有點像在二維數組上求最小值。但是這不可行。

我們有一個觀察：這個二維數組是一個下三角矩陣，且在同一列上，行越小，值越小。

我們又有一個觀察：我們每一次操作 \((x,y)\)，其實都是在這個數組上刪除左上角為 \((x,x)\)，右下角為 \((y,y)\) 的矩陣內的元素。

第二個觀察啟發我們一個點不能達到的位置一定是一個連續區間，且隨著下標的增加，不能到達的位置單調不降。

第一個觀察啟發我們，一個點到它可以達到的最左的點是距離最小的。

于是我們有一個回答詢問的方法：我們每一次先二分出 \([1,x]\) 內可以直接到達 \([y,n]\) 的最大位置 \(p\)，然后對 \([1,p]\)，詢問到 \(y\) 的最小值；對 \([p+1,x]\) 詢問到它們各自可以到達的最左位置的最小值。

那我們或許可以通過數據結構加速這個過程：如果我們可以知道一個點是否可以到達另一個點，且從一個點出發，到達最右的點的距離是多少，且在區間上合并第二個信息，我們就做完了。顯然，線段樹是一個好東西。

做修改時，我們可以通過線段樹二分找到當前修改的有效區間，然后對這個區間進行區間賦值，然后貪心地維護區間內到最左位置的最小距離即可。