树上信息统计

绝大多数时候，我们会统计树上联通信息，例如子树信息、链信息、邻域信息。

联通信息有时可以点边容斥。

虚树、子树、链、普通连通块通常在 $\rm lca$ 处统计，邻域通常在中心处合并。

O(1) 链 max

对树建极值分治树，等价于查询 $\rm lca$ 。

不以点数为体积的树上背包

树上启发式合并， $nk\log n$ 。

dsu on tree 可以视为树上扫描线

P8981 「DROI」Round 1 距离

若对于树上两点 $u,v$ ，满足 $\forall x \in G,\operatorname{dis}(u,x) \leq \operatorname{dis}(u,v)$ 且 $\operatorname{dis}(v,x) \leq \operatorname{dis}(u,v)$ ，那么我们称无序点对 $(u,v)$ 为极远点对。

同时，树 $G$ 上一点 $x$ 的权值 $v_x$ 定义为：满足两点间最短路径经过 $x$ 的极远点对的数量。

现给定树 $G$ ，求 $\sum\limits_{x \in G}{v_x^k}$ 对 $998244353$ 取模的值，其中 $k$ 是给定的常数，且 $k \in [1,2]$ 。

对于 $100\%$ 的数据，满足 $n \leq 5 \times 10^6$ ， $1 \leq k \leq 2$ 。

$u,v$ 都必须是直径端点。

P10678 『STA - R6』月

对于一棵有 $n$ 个节点的树 $T$ ，定义其直径 $\operatorname{diam}(T)$ 为任意两个节点之间距离的最大值。

给定正整数 $n$ 和每个点 $i$ 的度数 $d_i$ ，你需要构造一棵树 $T^\prime$ ，同时最小化 $\operatorname{diam}(T^\prime)$ 。

保证至少存在一棵符合要求的树，若存在多个符合要求的答案，输出任意一个即可。

对于 $100\%$ 的数据：

$2 \le n \le 2 \times 10^5$ ；

$1 \le T \le 10^5$ ；

$\sum n \le 2 \times 10^5$ ；

$1 \le d_i < n$ ；

保证至少存在一个合法的解。

首先变成最小化半径，即提点为根然后最小化深度。

调整法可以证明度数大的放上面更优，bfs 一下即可。

典

给定树，问有多少子集两两距离 $\le k$ 。

假装 $k$ 是偶数。

对于每个合法方案，我们把它映射到所有中心（到所有点距离不超过半径的点）构成的连通块上。

点边容斥，如果不理解正确性可以看柿子：

$\begin{aligned} &\sum_{合法点集}1 \\=&\sum_{合法点集}该点集对应的极大连通块的(点数-边数) \\=&\sum_{点}点集对该点合法-\sum_{边}点集对该边合法&\end{aligned}$

P6845 [CEOI2019] Dynamic Diameter

动态改边，动态求直径，保证正权，强制在线。

按照 dfn 排序，线段树维护区间直径，会被影响的区间是与 $[l,r]$ 有交但不包含的区间，这就是线段树上区间询问涉及到的区间，暴力重构区间的答案即可。

还要支持单点加链和，差分变成子树加单点查，单 $\log$ ，总复杂度 $q\log^2 n$ 。