Day 0001 0101。
考虑对每个点 \(u\) 计算贡献，求出所有经过它的路径的两个端点，包含这些点的最小连通块大小就是以 \(u\) 为端点的 \((u,v)\) 答案数对的个数。
根据经典结论，对于 \(m\) 个点的点集 \(u_1,u_2,\cdots ,u_m\)，钦定 \(u_0=u_m\) 且根据 DFS 序排序，则以任意点为根，包含它的最小连通块大小为 \(\sum\limits_{i=1}^md_{u_i}-d_{\text{lca}(u_i,u_{i-1})}\)。\(d_u\) 为 \(u\) 的深度。
发现如果知道所有经过 \(u\) 的路径的端点，再插入一条经过 \(u\) 的路径，\(u\) 的贡献也是容易通过在 DFS 序上建立线段树动态维护的。于是相当于 \(m\) 次链修改，每次修改在 \(u,v\) 之间的路径上的线段树插入点 \(u\) 和 \(v\)。
树上差分一下，变成单点修改。然后父亲节点的线段树需要从子节点继承而来，线段树合并即可。
使用 DFS 序求 LCA，复杂度 \(O(n\log n)\)。
标签：语言,线段,路径,DFS,修改,端点,ZJOI2019 From： https://www.cnblogs.com/Ender32k/p/17728600.html