题解 P5327 【[ZJOI2019]语言】

Sooke

2019-05-01 23:08:57

Solution

### 前言 先来扯些真实的废话。 这八成是考场上最可做的题,原因有以下: > 1. 众所周知,数据范围越不正常的题越毒瘤,本题的数据范围就很正常。 > > 2. 往年省选包括今年 round 1 最简单的题中往往都有线段树,本题感性上就离不开线段树。 > > 3. 九条在出完 2、3、1 的开题顺序之后,喜欢出 2、1、3 的开题顺序。 遗憾的是,由于 round 1 的爆炸,考场上心态有点崩,智商骤降为 0,导致没做出此题。 可能我永远属于入场思维受阻、出场茅塞顿开的那种人吧。 --- ### 解题思路 不难想到各种 $O(n \log^3 n)$ 的乱搞做法,比如链剖套扫描线 ,~~听说会被九条定向卡~~。 实际上有一种巧妙的 $O(n \log n)$ 清真做法。若城市 $u,\,v$ 能开展贸易,我们称 “ $u$ 可以到达 $v$ ”。 首先容易发现以下性质: > $u$ 能到达的所有点恰好构成一棵生成树(即一个连通块)。 考虑这个生成树是怎么来的?可以进一步得出: > 如果路径 $s \to t$ 包含点 $u$ ,$s,\,t$ 则是 $u$ 的两个极远点。 > > $u$ 的生成树则是连通所有 $u$ 的极远点的最小生成树。 举个例子,假设有三条路径分别是 $1 \to 3$ ,$2 \to 6$ ,$7 \to 8$ 。 ![](https://i.loli.net/2019/05/02/5cca3428c824e.png ) 锁定 $4$ 号点。路径 $1 \to 3$ 不经过它,对它没有任何贡献。其他路径则经过 $4$ 号点,表明其有 $4$ 个极远点:$2,\,6,\,7,\,8$ 。故生成树由 $2,\,4,\,5,\,6,\,7,\,8$ 构成,即 $4$ 号点能到达其他 $5$ 个不同的点。 于是,我们需要事先思考子问题:给定树上若干的点,如何求最小生成树大小? --- 这应该是个经典问题。可能要用到一点建虚树的思想。 为了方便,我们硬点存在极远点 $1$ ,最后再计算其影响。 我们给这些点按照 $\mathrm{dfs}$ 序排序,然后一个一个地加进去。假设当前加入 $u$ 号点,之前加入的点构成点集 $S$ ,$S$ 的最小生成树是 $T$。显然,为了使 $u$ 和 $T$ 连通,只需要找到 $T$ 中离 $u$ 最近的点连起来就好了,这“最近的点”正是 $S$ 中的某个点与 $u$ 的 $\mathrm{lca}$ 。如果你对 $\mathrm{dfs}$ 序有较好的感觉,其实所谓 $S$ 中的某个点,就是上一个加进去的点 $v$ !所以 $u$ 的贡献是 $\mathrm{dep}_u - \mathrm{dep}_{\mathrm{lca}(u,\,v)}$ 。别忘了硬点了 $1$ 号点,最后还要减 $\mathrm{dep}_{\text{所有点的}\ \mathrm{lca}}$ 。 上面那段可能有点绕,强烈建议画个图感受一下! 暴力加点似乎不容易被利用,此时最擅长分治的线段树终于重磅登场了。 仍然是以 $\mathrm{dfs}$ 序为下标,线段树的叶子结点控制原树上每个点选或不选,每个结点表示了硬点 $1$ 后一段区间的点集的最小生成树大小,并存下每个点集中下标最小和最大的点。类似地,$\mathrm{pushup}$ 时要减去 $\mathrm{dep}_{\mathrm{lca}(u,\,v)}$ 。此时的 $u$ 当然是左孩子已选下标最大的,$v$ 当然是右孩子已选下标最小的。查询的话只要用根结点的答案减去 $\mathrm{dep}_{\text{所有点的}\ \mathrm{lca}}$ 即可。 白白套一个线段树不是多 $\log$ 吗?别急,正解已经浮出水面了。 --- 想象每个结点都有一棵线段树。注意到有一条路径 $s \to t$ ,我们会给该路径上的每棵线段树都选上 $s,\,t$ 两点。按照套路,求出 $\mathrm{lca} = \mathrm{lca}(u,\,v)$ ,等同于 $s \to \mathrm{lca},\,t\to \mathrm{lca}$ 两条链上执行线段树修改。仍然是套路,链上修改可以转换成树上差分打标记,$s,\,t,\,\mathrm{lca},\,\mathrm{fa}[\mathrm{lca}]$ 分别打上 $1,\,1,\,-1,\,-1$ 。 慢着……线段树打标记是可以,但每个结点要把自己的信息继承给父亲,这怎么做? #### 动态开点 + 线段树合并! 至此,[[ZJOI2019]语言](https://www.luogu.org/problemnew/show/P5327) 的大致做法讲完了。$n$ 次线段树合并是 $O(n \log n)$ 的,而 $n$ 次修改要求 $n \log n$ 次 $\mathrm{lca}$ ,如果树剖或倍增,复杂度是 $O(n \log^2 n)$ ,如果使用欧拉序 $\mathrm{st}$ 表,复杂度是优美的 $O(n \log n)$ 。 --- ### 代码实现 刚才求的 $(u,\,v)$ 没有强制 $u < v$ ,答案要除以 $2$ 。 ```cpp #include <cmath> #include <cstdio> #include <vector> #include <algorithm> const int N = 200005, V = 6400005, L = 18; int n, m, tms, o[N], ft[N], dep[N], dfn[N], st[L][N]; std::vector<int> to[N], del[N]; long long ans; inline int getLca(int u, int v); struct SegmentTree { int tot, c[V], f[V], s[V], t[V], ls[V], rs[V], rt[N]; inline void pushUp(int u) { f[u] = f[ls[u]] + f[rs[u]] - dep[getLca(t[ls[u]], s[rs[u]])]; s[u] = s[ls[u]] ? s[ls[u]] : s[rs[u]]; t[u] = t[rs[u]] ? t[rs[u]] : t[ls[u]]; } inline int query(int u) { return f[u] - dep[getLca(s[u], t[u])]; } void modify(int &u, int l, int r, int p, int x) { if (!u) { u = ++tot; } if (l == r) { c[u] += x; f[u] = c[u] ? dep[p] : 0; s[u] = t[u] = c[u] ? p : 0; return; } int mid = l + r >> 1; if (dfn[p] <= mid) { modify(ls[u], l, mid, p, x); } else { modify(rs[u], mid + 1, r, p, x); } pushUp(u); } void merge(int &u, int v, int l, int r) { if (!u || !v) { u |= v; return; } if (l == r) { c[u] += c[v]; f[u] |= f[v]; s[u] |= s[v]; t[u] |= t[v]; return; } int mid = l + r >> 1; merge(ls[u], ls[v], l, mid); merge(rs[u], rs[v], mid + 1, r); pushUp(u); } } smt; void build() { for (int i = 1; i <= tms; i++) { o[i] = log(i) / log(2) + 1e-7; } for (int i = 1; i <= o[tms]; i++) { for (int j = 1, u, v; j + (1 << i) - 1 <= tms; j++) { u = st[i - 1][j]; v = st[i - 1][j + (1 << i - 1)]; st[i][j] = dep[u] < dep[v] ? u : v; } } } inline int getLca(int u, int v) { if (!u || !v) { return 0; } u = dfn[u]; v = dfn[v]; if (u > v) { std::swap(u, v); } int d = o[v - u + 1]; u = st[d][u]; v = st[d][v - (1 << d) + 1]; return dep[u] < dep[v] ? u : v; } void dfs(int u, int fa) { ft[u] = fa; dep[u] = dep[fa] + 1; st[0][++tms] = u; dfn[u] = tms; for (auto v : to[u]) { if (v != fa) { dfs(v, u); st[0][++tms] = u; } } } void solve(int u) { for (auto v : to[u]) { if (v != ft[u]) { solve(v); } } for (auto v : del[u]) { smt.modify(smt.rt[u], 1, tms, v, -1); } ans += smt.query(smt.rt[u]); smt.merge(smt.rt[ft[u]], smt.rt[u], 1, tms); } int main() { scanf("%d%d", &n, &m); for (int i = 2, u, v; i <= n; i++) { scanf("%d%d", &u, &v); to[u].push_back(v); to[v].push_back(u); } dfs(1, 0); build(); for (int u, v, lca; m; m--) { scanf("%d%d", &u, &v); lca = getLca(u, v); smt.modify(smt.rt[u], 1, tms, u, 1); smt.modify(smt.rt[u], 1, tms, v, 1); smt.modify(smt.rt[v], 1, tms, u, 1); smt.modify(smt.rt[v], 1, tms, v, 1); del[lca].push_back(u); del[ft[lca]].push_back(u); del[lca].push_back(v); del[ft[lca]].push_back(v); } solve(1); printf("%lld\n", ans >> 1); return 0; } ``` --- ### 尾注 看完后您还可真别说这题简单,考场上这么多算法的选择,鬼知道偏偏碰上了这一种呢?