P4219 [BJOI2014]大融合

题目大意

• 给定 $n$ 点, $m$ 个操作如下
  • 加入一条边，保证连边的两点原来不连通
  • 询问有多少条路径通过某条边
• $1 \leq n,m \leq 10^5$

分析

网上大多题解都是使用 LCT 来维护, 然而蒟蒻并不会 LCT, 所以这里提供一种仅使用树链剖分的解法.

不难发现某条边路径数为 $siz_x \times (siz_{root} - siz_x)$, 其中 $x$ 为边所连的点中深度较大的一个, $root$ 为树根, $siz$ 为子树大小.

发现最后 $n$ 个点的形态为一个森林, 所以我们可以先离线下来, 建好森林再倒序删边同时回答询问.

假设删去的边连接 $x, y$, 且 $x, y$ 原来的深度 $dep_x < dep_y$. 删边会影响 $x$ 到根路径上的点的子树大小, 以及以 $top_a$, 其中 $a$ 为 $y$ 所在重链中 $y$ 一下的节点.

我们可以用树剖来维护 $siz$ 和 $dep$, 断开边时, 将 $x$ 到根的路径上的点的 $siz$ 都减去 $siz_y$, 将 $x$ 一下的重链上节点的 $top$ 修改为 $y$. 查询时, $siz_y \times (siz_{root} - siz_y)$ 即为答案.

本做法为真·用树剖来维护树剖, 复杂度为 $O(m\log^2n)$, 还是很快的.

代码

只放出修改和查询时的核心代码, 细节较多, 注意更新 $dep$ 和 $siz$, 完整代码可以看我的提交

修改

fa[y] = 0;
top[y] = query(1, 1, n, dfn[y]).top;
top[x] = query(1, 1, n, dfn[x]).top;
// 更新 top
if(top[y] != y){
	modify(1, 1, n, dfn[y], dfn[y] + dep[tail[top[y]]] - dep[y], y); // 修改 y 所在重链 top
	top[y] = y;
	tail[top[y]] = tail[top[x]];
	tail[top[x]] = x;
}
siz[y] = query(1, 1, n, dfn[y]).siz; // 更新 siz
while(x){
	top[x] = query(1, 1, n, dfn[x]).top;
	mul(1, 1, n, dfn[top[x]], dfn[x], -siz[y]); // 修改 x 到根的 siz
	x = fa[top[x]];
}

查询

siz[y] = query(1, 1, n, dfn[y]).siz;
top[x] = query(1, 1, n, dfn[x]).top;
// 更新 siz 和 top
while(fa[top[x]]){
	x = fa[top[x]];
	top[x] = query(1, 1, n, dfn[x]).top;;
}
x = top[x];
// x 跳到根
siz[x] = query(1, 1, n, dfn[x]).siz;
ans[i] = 1LL * siz[y] * (siz[x] - siz[y]); //注意 long long