娃娃机毒瘤 qwq
题意简述：给定一棵\(n\)个点的有根树，\(m_a\)条\(a\)链和\(m_b\)条\(b\)链，保证任意一条链的端点之间存在祖先-后代关系。求\(\sum_{i=1}^{m_a} \sum_{j=1}^{m_b} f_p(a_i, b_j)\)，其中，
\[f(a, b)=\begin{cases} 0, &a \cap b=\varnothing\(|a\cap b|-1)^p, &\text{otherwise} \end{cases} \]
注意此处的交为点相交，且我们认为\(0^0=1\)。\(1\leq n, m_a, m_b\leq 10^5, p\in\{0, 1, 2\}\)。
对于\(p=1\)的情况，发现 \(f_1(a, b)=a,b\) 的边的交集。将\(a\)链树上差分，每条\(b\)链直接查询即可。
对于\(p=0\)的情况，发现 \(f_0(a, b)=a, b\) 的点的交集\(-f_1(a, b)\)。方法与\(p=1\)类似。
下面重点处理\(p=2\)的情况。
设红链形如\((u_i, v_i)\)，蓝链形如\((x_i, y_i)\)，其中\(u_i\)是\(v_i\)的祖先，\(x_i\)是\(y_i\)的祖先。我们可以只考虑\(x_i\)是\(u_i\)祖先的情况，剩余情况对称考虑即可，只需注意\(x_i=u_i\)时的去重。设交集非空的两条链\(a_i\)和\(b_j\)的交集中，深度\(dep\)最大的点为\(w\)，则\(f_2(a_i, b_j)=(dep_w-dep_{u_i})^2=dep_w^2+dep_{u_i}^2-2 dep_w\cdot dep_{u_i}\).
先对整棵树dfs，经过每个\(u_i\)时，维护\(x_j\)在\(u_i\)到根的路径中的蓝链的集合，考虑对以上三部分分别统计答案：
\(dep_{u_i}^2\)：由于当前dfs到了点\(u_i\)，可以直接计算\(dep_{u_i}^2\)。发现每存在一条蓝链与其相交，这部分贡献就会多算一次，因此直接树上差分计算\(u_i\)的子树中，\(y_j\)的数量即可。
\(-2dep_w\cdot dep_{u_i}\)：同样可以直接计算\(-2 dep_{u_I}\)，乘上\(\sum dep_w\)即可。\(\sum dep_w\)的统计可以在dfs进入\(x_i\)时，在\(x_i\)到\(y_i\)的链上\(+1\)，询问时直接求\(u_i\)到\(v_i\)的点权和即可。
[SOJ618] 小$\omega$的数据结构题【差分】【树链剖分】
原文：https://www.cnblogs.com/suwakow/p/11668177.html