树上最值路径 题解

题意简述

给你一棵 \(n\) 个结点的树，编号为 \(1 \sim n\)，求有多少路径 \(\operatorname{Path}(u \rightarrow v)\)，满足 \(u = \max \{ x \mid x \in \operatorname{Path}(u \rightarrow v) \}\)，\(v = \min \{ x \mid x \in \operatorname{Path}(u \rightarrow v) \}\)。

\(n \leq 2 \times 10^6\)。

题目分析

考虑从小到大的顺序枚举 \(u\)，去掉 \(\max\) 的限制，因为 \(u\) 必然是之前的点中的 \(\max\)，\(\min\) 从大到小扫同理。在加入 \(u\) 之前，这棵树是若干个联通块。\(u\) 和其相邻的联通块之中的任意一点 \(v\)，都能保证 \(u = \max \{ x \mid x \in \operatorname{Path}(u \rightarrow v) \}\)。我们考虑并查集缩点，每次在一棵新的树上，把代表联通块的点和 \(u\) 之间连一条边，并将其在并查集上的父亲设为 \(u\)。这实际上是一个重构树的过程，这个新树有一个很好的性质，那就是当且仅当 \(v\) 是 \(u\) 在新树上的所有后代，使得 \(u = \max \{ x \mid x \in \operatorname{Path}(u \rightarrow v) \}\)。我们将一个奇怪的最值限定，变成了树上祖先后代的限定。我们将这棵树称作 \(\max\) 树。

我们现在有了两棵重构树，分别满足 \(\min\) 和 \(\max\) 的限制。然后就要考虑如何统计答案了，也就是有多少对 \((u, v)\)，满足在 \(\max\) 树上，\(u\) 是 \(v\) 的祖先，在 \(\min\) 树上，\(v\) 是 \(u\) 的祖先。我们还是考虑枚举，在 \(\min\) 树上枚举一个 \(u\)，查询有多少 \(\min\) 树上 \(u\) 的祖先 \(v\)，满足在 \(\max\) 树上 \(v\) 是 \(u\) 的后代。祖先的限制可以用 dfs 栈的思想，用一个数据结构实时维护 dfs 栈中的元素。后者查询后代操作，可以用 dfs 序 + 树状数组区间查询。那么 dfs 栈就是树状数组的单点加操作。

时间复杂度：\(\Theta(n (\alpha(n) + \log n))\)

代码

#include <cstdio>
#include <iostream>
using namespace std;const int N = 2000010;struct Graph {struct node {int to, nxt;} edge[N << 1];int tot, head[N];inline void add(int u, int v) {edge[++tot] = {v, head[u]};head[u] = tot;}inline node & operator [] (int x) {return edge[x];}
} xym, yzh1, yzh2;int n;
long long ans;int fa[N];
int get(int x) {return fa[x] == x ? x : fa[x] = get(fa[x]);
}int tree[N];
inline void modify_add(int p) {for (int i = p; i <= n; i += i & -i)++tree[i];
}
inline void modify_sub(int p) {for (int i = p; i <= n; i += i & -i)--tree[i];
}
inline int query(int p) {int res = 0;for (int i = p; i; i &= i - 1)res += tree[i];return res;
}int L[N], R[N], timer;
void dfs(int now) {L[now] = ++timer;for (int i = yzh1.head[now]; i; i = yzh1[i].nxt)dfs(yzh1[i].to);R[now] = timer;
}void redfs(int now) {ans += query(R[now]) - query(L[now] - 1);modify_add(L[now]);for (int i = yzh2.head[now]; i; i = yzh2[i].nxt)redfs(yzh2[i].to);modify_sub(L[now]);
}signed main() {#ifndef XuYuemingfreopen("charity.in", "r", stdin);freopen("charity.out", "w", stdout);#endifscanf("%d", &n);for (int i = 1, f; i <= n; ++i) {scanf("%d", &f), fa[i] = i;if (f == 0) continue;xym.add(i, f), xym.add(f, i);}for (int u = 2; u <= n; ++u) {for (int i = xym.head[u]; i; i = xym[i].nxt) {int v = xym[i].to;if (v > u) continue;yzh2.add(u, v = get(v));fa[v] = u;}}for (int i = 1; i <= n; ++i) fa[i] = i;for (int u = n - 1; u >= 1; --u) {for (int i = xym.head[u]; i; i = xym[i].nxt) {int v = xym[i].to;if (v < u) continue;yzh1.add(u, v = get(v));fa[v] = u;}}dfs(1), redfs(n), printf("%lld", ans);return 0;
}