树上最值路径 题解

题意简述

给你一棵 \(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 XuYueming
	freopen("charity.in", "r", stdin);
	freopen("charity.out", "w", stdout);
	#endif
    scanf("%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;
}