题解 | #最大最小路#

1. 问题建模

给定一棵树 ，对于每一条简单路径 ，定义：

• 条件 ：
• 条件 ：

题目要求计算满足 的路径数量。

2. 算法：容斥原理

直接统计同时满足最小值和最大值界限的路径较为复杂。根据容斥原理，我们可以通过补集来简化计算。

令全集 为树上所有简单路径的集合。则： 根据容斥公式：

其中补集条件的含义如下：

• ：路径上所有节点的权值均满足 。
• ：路径上所有节点的权值均满足 。
• ：路径上所有节点的权值均满足 。

最终计算公式为：

3. 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr ll INF = 2e9;

struct DSU {
    vector<int> parent;
    vector<ll> sz;
    int n;

    DSU(int n): n(n) {
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0);
        sz.assign(n + 1, 1);
    }

    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }

    void unite(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx != ry) {
            parent[rx] = ry;
            sz[ry] += sz[rx];
        }
    }

    void reset(const vector<int>& active_nodes) {
        for (int i : active_nodes) {
            parent[i] = i;
            sz[i] = 1;
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll a, b;
    cin >> n >> a >> b;

    vector<ll> w(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    vector<pair<int, int>> edges;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        edges.emplace_back(u, v);
    }

    ll totalPaths = (ll)n * (n + 1) / 2;

    auto countPaths = [&](ll L, ll R)->ll {
        vector<int> active_nodes;
        for (int i = 1; i <= n; i++) {
            if (w[i] >= L && w[i] <= R) active_nodes.push_back(i);
        }
        static DSU dsu(n);
        dsu.reset(active_nodes);

        for (auto& edge : edges) {
            int u = edge.first;
            int v = edge.second;
            if (w[u] >= L && w[u] <= R && w[v] >= L && w[v] <= R) {
                dsu.unite(u, v);
            }
        }

        ll total = 0;
        for (int i = 1; i <= n; i++) {
            ll curSize = dsu.sz[i];
            if (dsu.parent[i] == i && w[i] >= L && w[i] <= R) {
                total += curSize * (curSize + 1) / 2;
            }
        }
        return total;
    };

    ll c1 = countPaths(a + 1, INF);
    ll c2 = countPaths(0, b - 1);
    ll c3 = countPaths(a + 1, b - 1);
    ll ans = totalPaths - c1 - c2 + c3;
    cout << ans << endl;
}

4. 复杂度分析

时间复杂度

• 初始化与全集计算：。
• 子图路径计数：
  • 每次计数需要遍历所有边（ 条）或仅遍历有效节点的邻接边。
  • 并查集操作（路径压缩 + 按秩合并）的复杂度为 ，其中 是反阿克曼函数。
• 总复杂度：。

空间复杂度

• 结构存储：邻接表映射 ，并查集数组 。
• 总复杂度：。