P11967 [GESP202503 八级] 割裂 题解

我讨厌倍增 lca, 因此提供一种非倍增做法。

首先我们先解析题意。相当于在一棵树上给你一条链 A,然后又给你一个有着若干条链的集合 B。问你在 A 上的节点有多少个不存在于集合 B 中的任意链上。

前置的一个知识是我们如何不利用倍增来找在一条链上的点。

我们发现，一个点 s 在链 x, y上，当且仅当

(lca(s,x) == s || lca(s,y) == s) && dep[s] >= dep[lca(x, y)]

自己手玩一棵树就可以得到，不讲解。

那么其实这题已经做完了。我们用树上差分处理出对于每个点, B 里的链经过这个点的次数。

然后判断通过刚才的方法判断这个点是不是在链 A 上。

lca 采用 \(O(1)\) lca。

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i <= b; ++i)
using namespace std;
const int N = 1000005;
int ans, n, a, x, y, z, target, cnt, b1, b2, dfn[N], dep[N], st[N][26], mark[N], father[N];
vector<int> e[N];
void dfs(int s, int fa) {father[s] = fa;dep[s] = dep[fa] + 1;dfn[s] = ++cnt;st[dfn[s]][0] = fa;for(const int to : e[s]) {if(to == fa) continue;dfs(to, s);}
}
inline int get(int x, int y) {return dep[x] < dep[y] ? x : y;}
void init() {for(int i = 1; (1 << i) <= n; ++i) {rep(j, 1, n) {if(j + (1 << i) - 1 > n) break;st[j][i] = get(st[j][i - 1], st[j + (1 << i - 1)][i - 1]);}}
}
inline int lca(int x, int y) {if(x == y) return x;x = dfn[x], y = dfn[y];if(x > y) swap(x, y);int len = __lg(y - x);return get(st[x + 1][len], st[y - (1 << len) + 1][len]);
}
void dfs2(int s) {for(const int to : e[s]) {if(to == father[s]) continue;dfs2(to);mark[s] += mark[to];}x = lca(s, b1), y = lca(s, b2);if(!mark[s] && ((x == s || (y == s))) && dep[s] >= dep[target]) ++ans;
}
int main() {cin >> n >> a;rep(i, 1, n - 1) {cin >> x >> y;e[x].push_back(y);e[y].push_back(x);}dfs(1, 0);init();rep(i, 1, a) {cin >> x >> y;z = lca(x, y);++mark[x], ++mark[y];--mark[z], --mark[father[z]];}cin >> b1 >> b2;target = lca(b1, b2);dfs2(1);cout << ans;return 0;
}

复杂度 \(O(n\log n + a)\)， 常数略大。