OI笔记 | 数 K-Cousin 的几种解法
在一棵树上，若存在一点 $z$ 是 $a$ 和 $b$ 共同的 $p$ 级祖先，则称 $a$ 和 $b$ 为 $p$ 级表亲。
给定一棵 $n$ 个点的树。有 $m$ 次询问，每次询问给出一对整数 $v$ 和 $p$，求编号为 $v$ 的人有多少个 $p$ 级表亲。
Solution 1
线段树合并，时空复杂度 $\mathcal{O}(n\log n)$。
可以通过 CF208E（$1\le n,m\le 10^5$）。
我们设 $x$ 的 $p$ 级祖先为 $F(x,p)$，则一组询问 $(v,p)$ 可以转化为 $F(v,p)$ 为根的子树中，有多少节点 $x$ 的 $dep_x=dep_v$。
那么可以在每一个节点 $u$ 上建立一棵权值线段树，然后把 $dep_u$ 加入线段树中。在 dfs 的同时做线段树合并，统计答案即可。
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
inline ll read() {...}
inline void write(ll x) {...}
const int MAX_N = 1e5 + 10, MAX_LOG = 18;
int cnt, n, m, ans[MAX_N], rt[MAX_N], fa[MAX_N][MAX_LOG], dep[MAX_N];
vector<int> rts, G[MAX_N];
vector<pii> qr[MAX_N];
// 权值线段树
struct node {int lc, rc, val;} d[MAX_N << 5];
inline int mid(int s, int t) {...}
inline void pu(int p) {...}
inline int update(int now, int s, int t, int v) {...}
inline int query(int now, int s, int t, int v) {...}
inline int merge(int u, int v, int s, int t) {...}
void dfs1(int u, int pre) {
dep[u] = dep[pre] + 1;
rt[u] = update(rt[u], 1, n, dep[u]);
fa[u][0] = pre;
for(int i = 1; i < MAX_LOG; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(int v : G[u])
dfs1(v, u);
}
int F(int u, int k) {...} // 倍增跳 k 级祖父
void dfs2(int u) {
for(int v : G[u]) {
dfs2(v);
rt[u] = merge(rt[u], rt[v], 1, n);
}
for(pii t : qr[u])
ans[t.first] = query(rt[u], 1, n, t.second) - 1;
}
int main() {
n = read();
for(int i = 1, r; i <= n; i++) {
r = read();
if(!r) rts.pb(i);
else G[r].pb(i);
}
for(int r : rts)
dfs1(r, 0);
m = read();
for(int i = 1, u, v, p; i <= m; i++) {
v = read(), p = read();
u = F(v, p);
qr[u].pb(make_pair(i, dep[u] + p));
}
for(int r : rts)
dfs2(r);
for(int i = 1; i <= m; i++)
write(ans[i]), putchar(" \n"[i == m]);
return 0;
}
这个做法并不能通过 洛谷 P5384（$1\le n,m\le 10^6$）。
考虑优化空间常数：
- 用链式前向星代替所有
std::vector。
下面是一个可复用的链式前向星模板：
struct link {
struct node {
int x, y, nxt;
node() {}
node(int _x, int _y, int _nxt) :
x(_x), y(_y), nxt(_nxt) {}
} t[MAX_N];
int fir[MAX_N], tot;
link() {memset(fir, 0, sizeof(fir)); tot = 0;}
inline void add(int u, int x, int y) {
t[++tot] = node(x, y, fir[u]);
fir[u] = tot;
}
inline int nxt(int now) {return t[now].nxt;}
inline pii info(int now) {return make_pair(t[now].x, t[now].y);}
} G, Q, qr;
- 用 dfs + 栈 $\mathcal{O}(n)$ 求 $k$ 级祖先。
void dfs2(int u) {
st[++top] = u;
for(int now = Q.fir[u]; now; now = Q.nxt(now)) {
pii T = Q.info(now);
if(top > T.second) {
int v = st[top - T.second], id = T.first;
qr.add(v, id, dep[u]);
}
}
for(int now = G.fir[u], v; now; now = G.nxt(now)) {
v = G.info(now).first;
dfs2(v);
}
--top;
}
- 优先遍历重儿子，且回收已经被合并的点。
如果做到了这些，理论上能卡过去了。但是我卡了两个小时都只有 $80pts$ 的好成绩，于是放弃。
Solution 2
对所有 $dep_0$ 开一个 std::vector，里面存上所有深度为 $dep_0$ 的点的 dfs 序。排序之后，每次只要二分一下区间端点即可。
时间复杂度 $\mathcal{O}(n\log n)$。只要预处理一下，把 std::vector 换成数组中的连续区间，空间就是严格 $\mathcal{O}(n)$ 的，可以通过此题。
Solution 3
计算答案相当于在 dfs 序的某个区间上数数，所以可以用树状数组来二维数点。时间复杂度 $\mathcal{O}(n\log n)$，空间复杂度 $\mathcal{O}(n)\sim \mathcal{O}(n\log n)$，取决于怎样求 $k$ 级祖先。由于常数很小，用倍增就可以卡过此题。
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
inline ll read() {...}
inline void write(ll x) {...}
const int MAX_N = 1e6 + 10, MAX_LOG = 18;
int n, m, dfncnt, siz[MAX_N], ans[MAX_N], fa[MAX_N][MAX_LOG], dep[MAX_N], dfn[MAX_N];
// 链式前向星
int tot, totQ, fir[MAX_N], firQ[MAX_N];
struct edge {int v, nxt;} E[MAX_N];
struct qr {int l, r, id, nxt;} Q[MAX_N];
inline void Clear() {...}
inline void AddEdge(int u, int v) {...}
inline void AddQr(int d, int l, int r, int id) {...}
struct TreeArray {...} T; // 树状数组
void dfs1(int u, int pre) {
dfn[u] = ++dfncnt;
dep[u] = dep[pre] + 1;
siz[u] = 1;
fa[u][0] = pre;
for(int i = 1; i < MAX_LOG; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(int i = fir[u]; i; i = E[i].nxt)
dfs1(E[i].v, u), siz[u] += siz[E[i].v];
}
int F(int u, int k) {...} // 倍增跳 k 级祖父
int main() {
n = read(), m = read();
for(int i = 1, r; i <= n - 1; i++) {
r = read();
AddEdge(r, i + 1);
}
dfs1(1, 0);
Clear();
for(int i = 1; i <= n; i++)
AddEdge(dep[i], i);
for(int i = 1, u, v, p; i <= m; i++) {
v = read(), p = read();
if(dep[v] <= p) continue;
u = F(v, p);
AddQr(dep[v], dfn[u], dfn[u] + siz[u] - 1, i);
}
for(int i = 1; i <= n; i++) {
for(int j = fir[i]; j; j = E[j].nxt)
T.update(dfn[E[j].v], 1);
for(int j = firQ[i]; j; j = Q[j].nxt)
ans[Q[j].id] = T.query(Q[j].r) - T.query(Q[j].l - 1) - 1;
for(int j = fir[i]; j; j = E[j].nxt)
T.update(dfn[E[j].v], -1);
}
for(int i = 1; i <= m; i++)
write(ans[i]), putchar(" \n"[i == m]);
return 0;
}
Solution 4
使用桶 + 树上差分代替树状数组。用 $cnt_x$ 表示已经 dfs 过的点中有多少个点的深度为 $x$。答案就是 dfs 当前子树前、dfs 当前子树后的 $cnt_{dep_v}$ 的差值。
时空复杂度 $\mathcal{O}(n)$，跑到了洛谷最优解前三名。
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
inline ll read() {...}
inline void write(ll x) {...}
const int MAX_N = 1e6 + 10;
int n, m, dfncnt, cnt[MAX_N], siz[MAX_N], ans[MAX_N], dep[MAX_N], dfn[MAX_N];
int st[MAX_N], top;
struct link {...} G, Q, qr; // 链式前向星
void dfs1(int u, int pre) {
st[++top] = u;
dfn[u] = ++dfncnt;
dep[u] = dep[pre] + 1;
siz[u] = 1;
for(int now = Q.fir[u]; now; now = Q.nxt(now)) {
pii T = Q.info(now);
if(top > T.second) {
int v = st[top - T.second], id = T.first;
qr.add(v, id, dep[u]);
}
}
for(int now = G.fir[u], v; now; now = G.nxt(now)) {
v = G.info(now).first;
dfs1(v, u);
siz[u] += siz[v];
}
--top;
}
void dfs2(int u) {
cnt[dep[u]]++;
for(int now = qr.fir[u]; now; now = qr.nxt(now)) {
pii T = qr.info(now);
ans[T.first] = cnt[T.second];
}
for(int now = G.fir[u], v; now; now = G.nxt(now)) {
v = G.info(now).first;
dfs2(v);
}
for(int now = qr.fir[u]; now; now = qr.nxt(now)) {
pii T = qr.info(now);
ans[T.first] = cnt[T.second] - ans[T.first];
}
}
int main() {
n = read(), m = read();
for(int i = 1, r; i <= n - 1; i++) {
r = read();
G.add(r, i + 1, 0);
}
for(int i = 1, u, v, p; i <= m; i++) {
v = read(), p = read();
Q.add(v, i, p);
}
dfs1(1, 0);
dfs2(1);
for(int i = 1; i <= m; i++)
write(max(ans[i] - 1, 0)), putchar(" \n"[i == m]);
return 0;
}
Solution 5
长链剖分优化 dp，待补充。
- 上一篇 OI笔记 | 2023.3 做题记录
- 下一篇 近期对 Blog 本身的小更新
♥