LXL tree tricks

CF1260F Colored Tree

给定一棵树，每个节点有一个颜色 $h$ ， $h_i$ 为 $[L_i,R_i]$ 内的一个整数。

现在，对于所有 $\prod (R_i-L_i+1)$ 种不同的染色方案，求出下列式子之和：

$\sum_{h_i=h_j,1\leq i<j\leq n}dis(i,j)$

$n\leq 10^5,1\leq L_i\leq R_i\leq 10^5$ ，答案对1e9+7取模。

首先变成概率，期望有累加性，每个点都要枚举不太好搞系数。

点分治 + 树状数组 $\log^2$ 。

扫描线换维利用 [LNOI2014] LCA 的做法可以 $\log^2$ ，这个做法感觉很强啊！！可以快速做 $\sum_{(i,j)}dis(i,j)$ 。

有神秘线段树合并做法，拆贡献拆到每条边上，我们要求子树与子树补的点积，可以用子树与全局的点积 $-$ 子树与本身的点积，前者可以提前求每个位置的全局权值，线段树自然求出全局和，后者只需维护全局平方和。

树上树链翻转

查出所有平衡树，将其全部 merge 后打上翻转标记后全部 split 再 merge 回原来的位置。

P5314 [Ynoi2011] ODT

维护链加，查询距离 $x\le 1$ 的点的 kth。

$n,m\le 10^6$ 。

平衡树维护轻儿子。

CF1172E Nauuo and ODT

给一颗大小为 $n$ （ $2\le n\le 4\cdot 10^5$ ）的树，每个点有一个颜色 $c_i$ （ $1\le c_i\le n$ ）

定义 $num(u,v)$ 为点 $u$ 到 $v$ 的路径上的颜色数。

现在希望你求出：

$\sum_{i=1}^n\sum_{j=1}^nnum(i,j)$

特别的，我们有 $m$ （ $1\le m\le 4\cdot 10^5$ ）次修改，每次修改一个点的点权，每次修改后，你都需要重新输出上值。注意，你仍然需要输出初始的答案。

所以你的输出应当为 $m+1$ 行。

这个题首先可以每个颜色单独算，所以其实是可以离线放到原树上做的，不要对着那个虚树硬维护。

那么现在变成只有黑白两色，操作有变色，求白连通块大小平方和。

这个时候可以根号做，度数分治，但是不好，我们考虑更好的。

考虑每个黑点截断了下方的白点，所以我们在黑点处统计平方和。

每次统计全局太困难了，我们考虑统计答案的变化量，就像莫队每次查全局很困难，但是动指针查变化很简单。

考虑维护每个白点子树里联通了多少白点，这个东西每次白变黑就找到上面最深的黑点（可以树剖维护 std::set，特判 begin 在不在上面，单 $\log$ ），然后做一个链减（链上问题下闭上开好文明）。

白变黑就先维护 $f$ ，然后答案的增量是 $\sum_{\text{v is son of x}} f_v^2 $ 以及上面的黑点的儿子的 $f^2$ ，所以现在等价于链加维护儿子 $f$ 平方和。

链加儿子 $f^2$ 和就跟链加 kth 一样做，搞一个变量记录轻儿子即可。