題目
對于給定的無向無根樹，第?i?個節點上有一個權值?wi??。我們定義一條簡單路徑是好的，當且僅當：路徑上的點的點權最小值小于等于?a?，路徑上的點的點權最大值大于等于?b?。
保證給定的?a<b，你需要計算有多少條簡單路徑是好的。
示例
輸入：
5 2 3 5 4 3 3 1 1 2 1 3 3 4 3 5第一行輸入三個整數 n,a,b(1≤n≤5×
,1≤a<b≤
)?代表節點數、給定的上下限。
第二行輸入?n?個整數 w1?,w2?,…,wn?(1≤wi?≤
此后?n?1?行，每行輸入兩個整數?u,v(1≤u,v≤n,uv)?代表一條無向邊連接樹上?u?和?v?兩個節點。
輸出：4
說明：對于這個樣例，如下圖所示。路徑 2→1→3→5 是好的，因為路徑點權最小值 1≦a 且點權最大值 5≧b。
除此之外，以下路徑也是好的： ?1→3→5； ?3→5； ?4→3→5。
分析
并查集+容斥原理
算法思路
統計總路徑數：
根據組合數學得到所有可能的簡單路徑數。n?個節點的樹中總路徑數（包含單節點路徑）可由組合公式計算：
分情況統計不好路徑：
如果一條路徑不好，則可能滿足：
-
全部節點權值均大于 a?——此時路徑的最小值大于 a；
-
全部節點權值均小于 b ——此時路徑的最大值小于 b。
利用并查集對滿足特定條件（全部節點權值大于 a，或全部節點權值小于 b，以及同時滿足這兩者的情況）構成的子圖進行連通分量劃分，進而統計每個連通分量內部所有路徑數量。
利用容斥原理：
計算好路徑數，確保重復扣除部分得到校正，從而求解出最終的答案。
時間復雜度：O()
空間復雜度：O()
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
using ll = long long;struct DSU {vector<int> parent, size;DSU(int n): parent(n+1), size(n+1, 1) {for (int i = 0; i <= n; ++i) parent[i] = i;}int find(int x) {return parent[x] == x ? x : parent[x] = find(parent[x]);}void unite(int a, int b) {a = find(a), b = find(b);if(a == b) return;if(size[a] < size[b]) swap(a, b);parent[b] = a;size[a] += size[b];}
};int main(){int n, a, b;cin >> n >> a >> b;vector<int> w(n+1);for (int i = 1; i <= n; ++i) cin >> w[i];vector<pair<int,int>> edges(n-1);for (int i = 0; i < n-1; ++i)cin >> edges[i].first >> edges[i].second;// 總路徑數（單節點路徑也算）ll total = (ll)n * (n+1) / 2;auto countComponentPaths = [&](auto &dsu, const vector<bool> &valid) -> ll {vector<int> comp(n+1, 0);for (int i = 1; i <= n; ++i)if(valid[i])comp[dsu.find(i)]++;ll sum = 0;for (int cnt : comp)if(cnt) sum += (ll)cnt * (cnt+1) / 2;return sum;};// DSU1：構造僅包含權值 > a 的子圖DSU dsu1(n);vector<bool> valid1(n+1, false);for (int i = 1; i <= n; ++i)valid1[i] = (w[i] > a);for (auto &e : edges) {if(valid1[e.first] && valid1[e.second])dsu1.unite(e.first, e.second);}// DSU2：構造僅包含權值 < b 的子圖DSU dsu2(n);vector<bool> valid2(n+1, false);for (int i = 1; i <= n; ++i)valid2[i] = (w[i] < b);for (auto &e : edges) {if(valid2[e.first] && valid2[e.second])dsu2.unite(e.first, e.second);}// DSU3：構造僅包含 a < 權值 < b 的子圖DSU dsu3(n);vector<bool> valid3(n+1, false);for (int i = 1; i <= n; ++i)valid3[i] = (w[i] > a && w[i] < b);for (auto &e : edges) {if(valid3[e.first] && valid3[e.second])dsu3.unite(e.first, e.second);}ll cnt1 = countComponentPaths(dsu1, valid1); // 所有節點均 > a 的路徑ll cnt2 = countComponentPaths(dsu2, valid2); // 所有節點均 < b 的路徑ll cnt3 = countComponentPaths(dsu3, valid3); // 同時均在 (a,b) 內 的路徑// 由于好路徑要求最小值<= a 且最大值>= b，因此// 不好路徑：所有節點均 > a 或所有節點均 < b// 但區間在 (a, b) 的部分被重復扣除，需加回來ll ans = total - cnt1 - cnt2 + cnt3;cout << ans << "\n";return 0;
}
