樹上莫隊，顧名思義，就是到樹上做莫隊。一般會有兩種寫法，一種是将莫隊正兒八經地搬到樹上做；另一種是将莫隊搬到樹的括号序上做。
樹上莫隊
這是在樹上分塊跑莫隊的版本。考慮到莫隊的實作過程，我們需要解決兩個問題：
如何對樹分塊，才能保證複雜度？
如何移動标記來實作轉移？
首先我們來解決第二個問題。
觀察序列莫隊的移動方式，我們發現它其實是将區間端點暴力移動到對應的新端點上；也即，如果我們目前統計了 \((u,v)\) 的答案，需要轉移到 \((u',v')\)，那麼我們可以将 \(u\) 暴力地移動到 \(u'\)，将 \(v\) 暴力地移動到 \(v'\)，複雜度則由分塊來保證。
定義集合的 \(\oplus\) 運算為 \(a\oplus b=a\cup b-a\cap b\)，容易驗證這個運算具有交換律、結合律和歸零律。
考察一下移動過程，我們維護目前路徑上的點集 \(s\)，那麼每次将指針從 \(p,p\in s\) 移走，我們就令 \(s=s\oplus\{p\}\)；同理，移到 \(q,q\not\in s\)，我們就令 \(s=s\oplus\{q\}\)。是以指針的移動對點集的影響可以用 \(\oplus\) 來描述。
設 \(p_{u,v}\) 為 \(u,v\) 路徑上的點組成的集合，設 \(r\) 為樹根。不難發現 \(p_{u,v}=p_{u,r}\oplus p_{v,r}\oplus \{\operatorname{lca}(u,v)\}\)。
設 \(p=\operatorname{lca}(u,v),q=\operatorname{lca}(u',v')\)，此時我們可以很好地構造具體操作過程：
\[\begin{aligned}p_{u',v'}
&=p_{u,v}\oplus{p_{u,v}}\oplus p_{u',v'}\\
&=(p_{u,r}\oplus p_{v,r}\oplus \{p\})\oplus(p_{u',r}\oplus p_{v',r}\oplus \{q\})\oplus p_{u,v}\\
&=(p_{u,r}\oplus p_{u',r})\oplus (p_{v,r}\oplus p_{v',r})\oplus \{p\}\oplus \{q\}\oplus p_{u,v}
\end{aligned}
\]
是以我們不難看出，我們應該對于 \(p_{u,u'}\) 上除開 \(\operatorname{lca}(u,u')\) 取異或，對于 \(p_{v,v'}\) 上除開 \(\operatorname{lca}(v,v')\) 取異或，此外再對 \(p,q\) 分别取異或，就可以從 \((u,u')\) 轉移到 \((v,v')\)。
不難發現端點在一個（不一定連通的）點集中移動的時候，單次移動複雜度取決于點集的直徑。是以，我們需要保證樹上的塊的直徑較小。設這個門檻值為 \(s\)，我們需要保證每個塊的直徑為 \(o(s)\)。
一種簡單的分塊方法是，我們對樹進行 dfs，用棧維護未被分塊的點。從某個兒子回溯的時候檢查目前棧中點數是否達到了 \(s\)，如果達到了 \(s\) 就退棧分塊；否則我們就将若幹個連續周遊的兒子的塊合并在一起，直到塊大小達到 \(s\) 再分塊；再不濟，這些點會和目前節點合并到一個塊中，并回溯到上一層。
注意，這裡需要将等待合并的兒子塊從棧中拿出來，不然會破壞直徑性質。
如果我們将兒子塊全部留到棧裡面，那麼相當于按照 dfs 序直接分塊，有可能出現如下情況：這樣如果先周遊 \(s-1\) 的子樹，那麼這 \(s-1\) 個點會和 \(u\) 合并，導緻直徑過大，複雜度不正确。 實作的時候不需要将剩餘的點彈出來，在進入某個節點的時候記錄目前的棧底即可。
樹上莫隊
這樣分塊，能夠保證每個塊大緻連通（最多隻缺一個 lca），同時可以保證塊的大小和直徑為 \(o(s)\)；并且每個點隻會被包含在一個塊中。
做莫隊的時候将所有詢問按照左端點的塊編号排序，編号相同的按照右端點的 dfs 序排序，之後按照上面所述的處理即可。
考慮這樣做的複雜度，分左端點和右端點：
單個塊内，左端點移動複雜度為 \(o(s)\)，總次數為 \(o(q)\)；
左端點換塊，左端點移動複雜度為 \(o(n)\)，總次數為 \(o(\frac{n}{s})\)。
左端點總複雜度為 \(o(qs+\frac{n^2}{s})\)。
左端點在一個塊内的時候，由于右端點按照 dfs 序排序，是以右端點移動相當于對樹進行 dfs 周遊，複雜度為 \(o(n)\)，總次數為 \(o(\frac{n}{s})\)，是以複雜度為 \(o(\frac{n^2}{s})\)。
得到複雜度為 \(o(qs+\frac{n^2}{s})\)，取 \(s=\sqrt{\frac{n^2}{q}}\) 得到最優複雜度為 \(o(n\sqrt{q})\)。
sp10707 cot2 - count on a tree ii
把上面說的寫一遍就好了，維護不同顔色的數量毫無難度。
括号序莫隊
待填坑