昨天 11:16 已编辑 ikun C++ 发布于北京

关注

第七届传智杯全国IT技能大赛程序设计赛道国赛（总决赛）—— 题解

A、研究生组用题：CDEFGH
B组用题：BCDEFG
C组用题：ABCDEF

补题链接：https://ac.nowcoder.com/acm/contest/108576

以下的代码均只给出了核心逻辑部分，并不是完整的代码。

同时代码中的 assert() 语句均为 std 编写过程中，充当validator的语句，提交时可以不写。

为了不产生歧义，这里给出以下 $\rm A-G$ 题代码的头文件部分：

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<ll, ll> P;
#define x first
#define y second
#define int long long

const int mod = 1e9 + 7;
const int pp = 998244353;

const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};

ll ksm(ll a, ll b, ll p) {
    ll ans = 1;
    a %= p;
    while(b) {
        if(b & 1) ans = (ans * a) % p;
        b >>= 1;
        a = (a * a) % p;
    }
    return ans % p;
}

A. 小苯的石子游戏

题意：

两个人轮流取石子，每次要么从奇数位置的石子堆里各取一个；要么从偶数位置的石子堆里各取一个；如果两种取法都没法取，则该玩家输掉游戏。判断谁胜谁负。

知识点：

思维，博弈，模拟。

题解：

注意到，取不了的情况实际上是对应着要取的位置中存在数字 $0$ 的情况。也就是说要取的石子堆里没有石子了，就取不了了。

那我们首先考虑一个简单的子问题：给定一个数组，两人轮流操作，每个人每次的操作都是给所有数字减一。问谁能先让数组出现 $0$ 。

显然结果是固定的，即我们只需要看数组的最小值即可，如果其是奇数，则先手可以，最小值是偶数则是后手可以。

那么考虑，我们本题实际上就是两个上述子问题加起来的结果，因此我们直接分别统计奇偶位置的最小值，加起来判断奇偶性即可。

代码：

void solve() {
    int n;
    cin >> n;
    assert(n <= 2e5);
    int odd = 1e9, even = 1e9;
    for(int i = 1, x; i <= n; i++) {
        cin >> x;
        assert(1 <= x && x <= 1e9);
        if(i & 1) {
            odd = min(odd, x);
        } else {
            even = min(even, x);
        }
    }
    if((odd + even) % 2) {
        cout << "BEN" << endl;
    } else {
        cout << "GEGE" << endl;
    }
}

时间复杂度： $\rm O(n)$ 。

B. 小苯的木棍切割

题意：

给定一个数组，每次所有数字减去数组中的最小值，数组中为 $0$ 的数字被删除。

求上述过程中，单次操作减去的数字总和最大的一次减去的数字总和。

知识点：

枚举， $sort$ 。

题解：

由于每次减去的是数组中的最小值，因此我们直接对数组排序，每次所有数字砍掉 $a_1$ 。

我们会发现，第一次每个数字都减去 $a_1$ ，第二次每个数字都减去 $a_2$ ，但此时 $a_2$ 是第一次操作之后的，因此实际上是 $a_2-a_1$ ，第三次减去的是 $a_3$ ，但此时 $a_3$ 是前两次操作后剩下的，实际上我们会发现就是 $a_3-a_2$ 。

因此我们得出结论，第 $i$ 次操作，所有数字减去的都是 $a_i-a_{i-1}$ 。

而第 $i$ 次操作有 $(n-i+1)$ 个数字参与减法了，因此我们枚举一遍取两者乘积的 $max$ 即可。

代码：

void solve() {
    int n;
    cin >> n;
    assert(n <= 2e5);
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        assert(a[i] <= 1e9);
        assert(a[i] >= 1);
    }
    sort(a.begin() + 1, a.end());

    int ans = 0;
    for(int i = 1; i <= n; i++) {
        ans = max(ans, (a[i] - a[i - 1]) * (n - i + 1));
    }
    cout << ans << endl;
}

时间复杂度： $\rm O(n*log(n))$ 。

C.大苯营

题意：

多组查询，给定正整数 $x$ ，找出 $y\ (x \ne y, 1\leq y <2^{31})$ ，满足： $x|y,x \oplus y, gcd(x,y)$ 恰好能构成一个非退化三角形。

知识点：

构造，位运算， $\gcd$ 。

题解：

小清新构造题，注意到，我们考虑一些特殊的情况，比如等腰三角形，因此我们尝试从三个数字中取两个相等的出来。

不难发现可以取 $x|y$ 和 $x\oplus y$ ，当 $x$ 和 $y$ 的二进制没有任何交集时（即 $x\&y=0$ 时）， $x|y=x\oplus y$ 。

此时有： $x|y = x\oplus y \geq \max(x,y)$ 。

同时有： $\gcd(x,y)\leq \min(x,y)$ 。

因此一定满足：两边之和大于第三边 $(x|y) + (x\oplus y)>\gcd(x,y)$ 。

一定能构成三角形。

因此我们只需要取整数 $x$ 在 $31$ 以内的任意 $0$ 位 $j$ ，答案 $y$ 就可以取 $2^j$ ，当然，把这些 $0$ 位全取上也是可以的。

代码：

void solve() {
    int x;
    cin >> x;

    int y = 0;
    for(int i = 30; i >= 0; i--) {
        if(x >> i & 1) {
            
        } else {
            y |= (1LL << i);
        }
    }
    if(y == 0) {
        y = -1;
    }

    cout << y << endl;
}

时间复杂度： $O(\rm T\times log(x))$ 。

（如果不存在 $0$ 位，则无解，即此时 $x$ 的二进制全为 $1$ 。）

D. 小苯的排列数

题意：

定义一个数字是 "排列数"，当且仅当这个数字的十进制每一位提出来，分离成一个数组以后，数组恰好是一个 $1$ 到 "数位长度"的排列。多组询问每次给定区间，找任意一个区间内的 "排列数" 并输出。

知识点：

全排列枚举，二分 / 分类大讨论，贪心。

题解：

首先本题应该有一个分类讨论+贪心的做法，从 $l$ 最高位开始每次尝试取最小的，如果没办法取下一个则回溯反悔的做法。该做法实现比较困难，且细节繁多，代码量大。

这里给出一个简单做法，实际上我们会发现 "排列数" 很少，只有 $1!+2!+...+9!$ 这么多个。

因此我们可以直接进行一个预处理，将所有的排列数都搜出来，这一步使用 $\rm next\_permutation$ 函数即可，存入数组后排序，接下来每次查询只需要二分不小于 $l$ 的最小 "排列数"，只要结果在 $r$ 以内即可。

代码：

vector<int> v;
void init() {
    auto trans = [&](vector<int> & p) -> int {
        int ans = 0;
        for(auto & x : p) {
            ans = (ans * 10) + x;
        }
        return ans;
    };

    for(int len = 1; len <= 9; len++) {
        vector<int> p;
        for(int j = 1; j <= len; j++) {
            p.emplace_back(j);
        }
        do {
            v.emplace_back(trans(p));
        } while(next_permutation(p.begin(), p.end()));
    }
    sort(v.begin(), v.end());
}

void solve() {
    int L, R;
    cin >> L >> R;
    auto it = lower_bound(v.begin(), v.end(), L);
    if(it != v.end() && *it <= R) {
        cout << *(it) << endl;
    } else {
        cout << -1 << endl;
    }
}

时间复杂度： $\rm O(k*log(k) + T*log(X))$ 。（其中 $k=1!+2!+...+9!$ ， $X=max(R)$ ）。

E. 小苯的字符串染色

题意：

给定 $01$ 串，要求恰好对 $k$ 个不同的位置进行 $flip$ （反转）操作，求最终连续相同段的最大长度。

知识点：

思维，分类讨论，贪心，双指针。

题解：

首先，由于题目求的是纯色子串，而只有两种颜色，因此我们不妨钦定求最长白色子串（即 ' $1$ '）的长度。实现了这一逻辑后，我们把输入的串全部 $flip$ 一遍再求一次，就得到了求最长黑色的答案。

因此我们只需要实现求最长连续 $1$ 的长度的逻辑即可。

我们发现，题目要求的是，要恰好染 $k$ 个不同位置，"恰好" 和 "不同" 都是关键点，我们一起来看。

$\bullet$ 如果串中 $0$ 的个数小于等于 $k$ ，那么贪心地，不难发现的是我们肯定全部用这 $k$ 次机会把一些 $0$ 变成 $1$ ，而不会去碰那些已经固定的 $1$ 。因此在这样的情况下，问题变成了，我们要选择一个尽可能长的区间，使得区间中恰好包含 $k$ 个 $0$ ，把这些 $0$ 染色就得到了这个区间长度作为答案。这实际上是一个非常经典的问题，我们直接双指针维护即可。

$\bullet$ 那么问题来到了，如果 $k$ 大于 $0$ 的个数呢？此时，由于我们是要 $1$ 尽可能多，因此我们肯定会先把所有 $0$ 变成 $1$ ，相当于字符串变成全 $1$ ，再把 $k$ 减去原本 $0$ 的个数。此时，对于这个全 $1$ 的字符串，由于 $k$ 还没用完，因此我们不得不选择一些 $1$ 把它们变成 $0$ 。

由于选择的位置不能重复，因此我们发现原本数组中的 $0$ 是不能选的，问题变成了：有一些位置上的 $1$ （原本是 $1$ 的位置）我们需要选择 $k$ 个，把他们变成 $0$ ，最大化连续 $1$ 的长度。这个问题，我们反向考虑即可，实际上是，选择一段尽可能长的区间，使得区间中恰好包含了 $C1-k$ 个 $1$ 。并且这些 $C1-k$ 个 $1$ 都是原本在字符串中就是 $1$ 的那些位置。（其中 $C1$ 是原本字符串中 $1$ 总的个数。）那么到这里相信问题已经变的十分明朗了，这个问题本质上和上一种情况一致。都是用双指针维护区间，使得区间中恰好包含若干个 $1/0$ 。

最终的区间长度就是答案。

做好上述函数功能，我们 $flip$ 一遍字符串再次求解取 $max$ 就是答案了。

代码：

void solve() {
    int n, K;
    string s;
    cin >> n >> K >> s;
    
    auto work = [&](string s) -> int {
        s = " " + s;
        int X = 0, Y = 0, k = K;
        for(int i = 1; i <= n; i++) {
            X += (s[i] == '0');
            Y += (s[i] == '1');
        }

        int ans = 0;
        if(k > X) {
            k -= X;
            Y -= k;
            // cerr << "Y : " << Y << ", k : " << k << endl;
            int cnt = 0;
            for(int i = 1, j = 1; i <= n; i++) {
                cnt += (s[i] == '1');
                while(cnt > Y && j <= i) {
                    if(s[j] == '1') {
                        cnt -- ;
                    }
                    j ++ ;
                }
                if(cnt == Y && j <= i) {
                    ans = max(ans, i - j + 1);
                }
            }
            return ans;
        }

        X = 0;
        for(int i = 1, j = 1; i <= n; i++) {
            X += (s[i] == '0');
            while(X > k && j <= i) {
                if(s[j] == '0') {
                    X -- ;
                }
                j ++ ;
            }
            if(j <= i && X == k) {
                ans = max(ans, i - j + 1);
            }
        }
        return ans;
    };

    int ans = work(s);
    for(int i = 0; i < n; i++) { // flip 一遍
        s[i] ^= 1;
    }
    ans = max(ans, work(s));

    cout << ans << endl;
}

时间复杂度： $\rm O(n)$ 。

F-小苯的物理小球

题意：

给定二维平面上一些和 $x$ 轴平行的线段，再给定一些自由落体的小球坐标，表示每次查询。如果小球落在线段上，会有 $50\%$ 的概率向左/右移动，从线段的一端滚下继续自由落体，直到落在地面上 $y=0$ 。

查询所有小球落在地面上时 $x$ 横坐标的期望之和。

知识点：

$set$ ，二分，双指针，离线 / 建 $dag$ 跑拓扑排序 $dp$ / 记忆化搜索。

题解：

本题有很多做法，例如建 $dag$ ，在 $dag$ 上 $dp$ ，再回答每次查询。这里给出 $std$ 的做法，用 $set$ 维护 $dp$ 数组。

实现上，我们开一个 $set$ 来维护所有可能 $dp$ 状态，实际上是一个 $pair$ ，存 $<$ 小球横坐标, 这个横坐标的期望 $>$ 。

首先我们离线所有的查询，然后我们对整个过程按 $y$ 从大到小，即从上到下维护，每次枚举我们都把上次枚举到这次之间的所有查询的坐标塞入 $set$ ，对应期望是 $1$ 。

我们只枚举那些有线段的层，这样一来枚举的层数就不会超过 $n$ ，对于一层的所有线段，我们枚举所有的线段，在维护的 $set$ 中找到被当前线段包含的所有点的坐标和对应期望，将期望求和后除以二，分别变成 $(l,y), (r,y)$ 这两个点扔到 $set$ 里，即给 $set$ 扔： $(l, \frac{sum}{2})$ 和 $(r, \frac{sum}{2})$ 这两个状态。

不停枚举到 $y=0$ 即可。

最终我们将 $set\ dp$ 中所有的状态对应的横坐标乘上对应的期望求和即是答案。

本题难点在代码实现。

代码：

void solve() {
    int n, m;
    cin >> n >> m;
    map<int, vector<P>> mp;
    for(int i = 0, l, r, y; i < n; i++) {
        cin >> l >> r >> y;
        mp[y].emplace_back(l, r);
    }
    int inv = ksm(2LL, MOD - 2, MOD);
    map<int, vector<int>> point;
    for(int i = 0, x, y; i < m; i++) {
        cin >> x >> y;
        point[y].emplace_back(x);
    }
    
    vector<vector<P>> a;
    vector<int> step;
    for(auto & [y, v] : mp) {
        sort(v.begin(), v.end());
        a.emplace_back(v);
        step.emplace_back(y);
    }
    while(step.size() && step.back() > (point.rbegin()->first)) {
        step.pop_back();
        a.pop_back();
    }
    reverse(a.begin(), a.end());
    reverse(step.begin(), step.end());
    int N = a.size();

    vector<int> point_y;
    vector<vector<int>> point_x;
    for(auto & [y, p] : point) {
        point_y.emplace_back(y);
        point_x.emplace_back(p);
    }

    set<P> dp;
    for(int i = 0; i < N; i++) {
        auto & v = a[i];
        int Y = step[i];
        while(point_y.size() && point_y.back() >= Y) {
            for(auto & x : (point_x.back())) {
                dp.emplace(x, 1);
            }
            point_x.pop_back();
            point_y.pop_back();
        }
        for(auto & [l, r] : v) {
            P lp = {l + 1, -1};
            P rp = {r, -1};
            auto L = dp.lower_bound(lp), R = dp.lower_bound(rp);
            // if(L == R) continue;
            vector<P> del;
            int sum = 0;
            for(auto it = L; it != R; it++) {
                sum += it->second;
                sum %= MOD;
                del.emplace_back(*it);
            }
            sum = (sum * inv) % MOD;
            for(auto & p : del) {
                dp.erase(p);
            }
            dp.emplace(l, sum);
            dp.emplace(r, sum);
        }
    }
    while(point_y.size()) {
        for(auto & x : point_x.back()) {
            dp.emplace(x, 1);
        }
        point_x.pop_back();
        point_y.pop_back();
    }

    int ans = 0;
    for(auto & [x, y] : dp) {
        ans += x * y % MOD;
        ans %= MOD;
    }
    assert(ans <= 1e9);
    cout << ans << endl;
}

时间复杂度： $\rm O((n+q)*log(n+q))$ 。

$\rm Bonus：$ 本题还有一些很好实现的做法，读者可以自行思考。

G. 小苯的地下城寻宝

题意：

给定 $n$ 点的树，每个点有一个数字，现要选一个点集，满足以下所有条件：

$\bullet\ 1$ 号点一定选；

$\bullet$ 点集中所有点的深度不同；

$\bullet$ 按照深度对点集排序后，相邻两点的数字都满足 $gcd>1$ ，即不互素；

求不同的点集个数。

知识点：

$\rm dp$ ，容斥， $\rm BFS$ 序

题解：

不难发现地下城实际上是一棵树，因为我们只对不同的深度对应的点感兴趣，因此我们先跑个 $\rm BFS$ 可以直接按照深度 $dep$ 将点都存起来，本质上其实就是 $\rm BFS$ 序，存到一个二维数组 $g_{i,j}$ 中，其中 $g_i$ 就表示所有深度为 $i$ 的点们组成的 $vector$ 。

接着我们把这个数组当成一个类似二维矩阵的东西，每个 $g_i$ 实际上都是二维矩阵中的一列，只是与之不同的是 $g$ 这个”矩阵“每一列的长度不一定相同，我们对每一列单独做 $dp$ 转移。

具体的，我们定义 $dp_i$ 表示考虑到 $i$ 号点并且路径以 $i$ 号点结尾（即最后一个取的是 $i$ 号房间的宝藏）的方案数，则我们转移需要用上层的 $dp$ 值来转移，但这里我们并不能直接暴力转移，否则再枚举上层点后复杂度会退化到平方级别，我们考虑存储一个 $sum$ 数组，其中 $sum_j$ 表示考虑到上一层结束的时候，所有 $a$ 值（即宝藏数量）为 $j$ 的倍数那些房间的 $dp$ 值之和。这样一来我们转移时只需要枚举 $a_i$ 的因子 $fac$ ，将其对应的 $\rm sum_{fac} \times coef_{fac}$ 加上即可，这里需要容斥的转移，因此我们提前处理一个容斥系数 $coef_i$ 即可。

在将一整层的 $dp_i$ 都转移完后，我们还需要更新 $sum$ 数组，因此我们需要一个 $map$ 来记录这一层所有 $dp$ 值对 $sum$ 的贡献。

执行完所有转移后， $\sum_{i=1}^ndp_i$ 就是答案，注意由于第一个点必须选，因此我们初始化 $dp_1=1$ 即可。

代码：

const int m = 1e5;
vector<int> coef(m + 1, 1);
vector<vector<int>> d(m + 1);
void init(int n) {
    coef[1] = 0;
    for(int i = 1; i <= n; i++) { // 预处理 j 的所有因子 d[j]
        for(int j = i; j <= n; j += i) {
            d[j].emplace_back(i);
            if(j > i) {
                coef[j] -= coef[i]; // 预处理容斥系数
            }
        }
    }
    int idx = -1, mx = 0;
    for(int i = 1; i <= n; i++) {
        if(d[i].size() > mx) {
            mx = d[i].size();
            idx = i;
        }
    }
}

void solve() {
    int n;
    cin >> n;
    assert(n <= 1e5);
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        assert(a[i] <= n);
        assert(a[i] >= 1);
    }

    vector<vector<int>> t(n + 1);
    vector<int> fa(n + 1);
    for(int i = 1, f; i <= n; i++) {
        cin >> f;
        fa[i] = f;
        assert(f >= 0);
        if(i == 1) {
            assert(f == 0);
        }
        assert(f <= n);
        t[f].emplace_back(i);
    }

    vector<int> dep(n + 1, -1);
    vector<vector<int>> g(n + 1);
    queue<int> q;
    q.emplace(1);
    while(q.size()) {
        auto u = q.front();
        dep[u] = dep[fa[u]] + 1;
        g[dep[u]].emplace_back(u);
        q.pop();
        for(auto & v : t[u]) {
            q.emplace(v);
        }
    }

    while(g.back().size() == 0) {
        g.pop_back();
    }

    vector<ll> dp(n + 1), s(n + 1);
    // dp[i] : 以 i 号点结尾的所有合法路径条数
    // s[j] : 一层层考虑到当前时，a 值为 j 倍数的 dp 值之和
    dp[1] = 1;
    for(auto & vec : g) {
        unordered_map<int, ll> ns;
        for(auto & u : vec) {
            for(auto & fac : d[a[u]]) {
                dp[u] += s[fac] * coef[fac];
                dp[u] = (dp[u] % MOD + MOD) % MOD;
            }
            if(dp[u] > 0) {
                for(auto & fac : d[a[u]]) {
                    ns[fac] += dp[u];
                    ns[fac] %= MOD;
                }
            }
        }
        for(auto & [dp_val, cnt] : ns) {
            s[dp_val] += cnt;
            s[dp_val] %= MOD;
        }
    }

    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        ans += dp[i];
        ans %= MOD;
    }
    cout << ans << endl;
}

/*



*/

signed main () {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    init(m);
    int _ = 1;
    cin >> _;
    while(_ -- ) {
        solve();
    }
    return 0;
}

时间复杂度： $\rm O(n*d_n*log(d_n))$ ，其中 $d_n$ 表示 $n$ 以内因子个数最多数字的因子， $\rm d_{10^5} < 200$ ， $log$ 的复杂度源自 $map$ ，本题没有卡 $unordered\_map$ ，实测会比 $map$ 快一些。

H. 智乃的 $\rm QTree\ Problem$

题意：

给定 $n$ 点的树，求满足端点权值差不大于 $l$ 的所有简单路径的极差之和

知识点：

启发式合并，并查集，线段树，笛卡尔树，（树分治）

题解：

首先可以一眼树分治，但是代码实现起来难度较高，可以使用毛毛虫火箭战术硬堆数据结构，验题人使用了树分治方法通过。

首先注意到 $\sum \limits_{i=1}^{n}\sum \limits_{j=1}^{n}Val(i,j)=max_{u,v\in Path(s,t)}\{a_u-a_v\} =max_{u\in Path(i,j)}\{a_u\}-min_{v\in Path(i,j)}\{a_v\}$ ，即极大值和极小值没必要同时算出，可以先求所有路径的极大值计算正贡献，减去所有路径的最小值计算负贡献。

然后接下来我们像剥洋葱一样，做如下的思维过程

$1.$ 将树上问题放到数组中考虑

$2.$ 思考一个限制条件的参数为特殊值时的更简单版本问题

对于这个题来说， $1.$ 是常见的解题思路，毕竟一个 $\rm QTree$ 问题如果数组上解不了，那么树上一定解不了，因为树包括单链。对于 $2.$ 考虑参数 $l$ 的特殊值，无非就两个， $0$ 或者 $inf$ ，这里考虑 $0$ 对于解题没有太大帮助，会使问题转换成 $\rm RMQ$ ，所以考虑 $l$ 是 $inf$ 的情况，即没有限制条件，改成求全部的区间/简单路径。

$l=inf$ 的情况

转化后的更简单版本的问题是：在数组上求 $\sum \limits_{i=1}^{n}\sum \limits_{j=i}^{n}max\{a_i,a_{i+1},...,a_{j}\}-min\{a_i,a_{i+1},...,a_{j}\}$

还是拆开，先求 $\sum \limits_{i=1}^{n}\sum \limits_{j=i}^{n}max\{a_i,a_{i+1},...,a_{j}\}$ ，这个问题显然是一个分治算法，但这个分治貌似并不需要从数组的中间切开，因为这样做很麻烦，需要维护前后缀的多个信息。但是只要每次找到数组的最大值 $a_{max}$ ，假设它的下标是 $x$ ，数组长度是 $n$ ，那么 $a_{max}$ 一定是 $(x)\cdot (n-x+1)$ 个区间的最大值，并且求完以后数组被分成了两个新的区间，然后继续递归处理。

该算法过程也被称为笛卡尔树，是一种将 $\rm RMQ$ 问题与 $\rm LCA$ 问题相互转化的手段。

$l\neq inf$ 的情况

注意到刚刚 $l=inf$ 的情况，实际上我们没有实际遍历分治划分的子区间，我们直接得到了 $(x)\cdot (n-x+1)$ ，现在有一个 $l$ 的限制条件，那我们可以做一个完整的分治算法，将分治区间的其中一侧使用权值线段树维护，另一侧查询权值线段树 $[a_i-l,a_i+l]$ 这段区间有多少元素。

做完了么？

并没有，因为这个分治算法并不是从中间均匀切开，这将导致不允许我们遍历分治两侧的较大区间，否则复杂度将退化为 $n^2$ 。

考虑这么一个经典问题，每次合并两段区间，但是合并的时候需要遍历较小一侧区间，时间复杂度是 $O(nlogn)$ ，这种思想被称为启发式合并。

所以可以在一开始，就先建好 $n$ 棵线段树，然后在分治返回合并区间的时候，暴力遍历尺寸较小的线段树，将线段树中的元素往大线段树里面合并。

本题的两种代码实现

$1.$ 使用多颗动态开点线段树，或者使用线段树合并的技巧

$2.$ 建立真的笛卡尔树，在笛卡尔树上使用 $\rm dsu\ on\ tree$ 算法，这样的好处是不需要动态开点，并且只有 $1$ 棵线段树，且该写法的常数较小

考虑放到树上

注意到这个算法好像天然就支持树上，无需编写额外代码支持树上操作。

从上述思考过程中得到的启示，既然数组上并不一定中分，而是从极值处分开更好实现，那么放到树上，同样也是不使用重心做树分治，而是按照极值切分

本题的核心 $\rm trick$ 是在分治算法中，如果不需要对分治较大一侧做枚举操作，则没必要均等划分两个分治的子集，尤其是在考虑 $\rm max,min$ 的场景下，按照极值划分会使问题变得更简单。

代码：

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 200005;
const int M = 6e4;

class segmentTreeMgr
{
private:
    struct Node
    {
        int sum, ch[2];
    };
    int tot, _N;
    vector<Node> data;
    stack<int> stk;

    int _query(const int root, const int l, const int r, const int L, const int R)
    {
        if (!root)return 0;
        if (L == l && R == r)return data[root].sum;
        int mid = (L + R) >> 1;
        if (r <= mid)return _query(data[root].ch[0], l, r, L, mid);
        else if (l > mid)return _query(data[root].ch[1], l, r, mid + 1, R);
        else return _query(data[root].ch[0], l, mid, L, mid) + _query(data[root].ch[1], mid + 1, r, mid + 1, R);
    }

    void _dump(const int root, vector<pair<int, int>> &v, const int L, const int R)
    {
        if (L == R)
        {
            v.emplace_back(L, data[root].sum);
            return;
        }
        int mid = (L + R) >> 1;
        if (data[root].ch[0])_dump(data[root].ch[0], v, L, mid);
        if (data[root].ch[1])_dump(data[root].ch[1], v, mid + 1, R);
    }

    void _add(int &root, const int pos, const int v, const int L, const int R)
    {
        if (!root)root = newNode();
        if (L == R)
        {
            data[root].sum += v;
            return;
        }
        int mid = (L + R) >> 1;
        if (pos <= mid)_add(data[root].ch[0], pos, v, L, mid);
        else _add(data[root].ch[1], pos, v, mid + 1, R);
        data[root].sum = data[data[root].ch[0]].sum + data[data[root].ch[1]].sum;
    }

public:
    explicit segmentTreeMgr(int N)
    {
        _N = N;
        tot = 0;
        data.resize(N * 64);
    }

    int newNode()
    {
        int ret;
        if (!stk.empty())
        {
            ret = stk.top();
            stk.pop();
        } else
        {
            ret = ++tot;
            assert(tot < data.size());
        }
        memset(&data[ret], 0, sizeof(Node));
        return ret;
    }

    void remove(int root)
    {
        if (data[root].ch[0])remove(data[root].ch[0]);
        if (data[root].ch[1])remove(data[root].ch[1]);
        stk.push(root);
    }

    void dump(int root, vector<pair<int, int>> &v)
    {
        _dump(root, v, 1, _N);
    }

    int query(int root, int l, int r)
    {
        l = max(l, 1);
        r = min(r, _N);
        return _query(root, l, r, 1, _N);
    }

    void add(int &root, int pos, int v)
    {
        _add(root, pos, v, 1, _N);
    }

    void clear()
    {
        tot = 0;
        while (!stk.empty())stk.pop();
    }
};

int n, k;
pair<int, int> a[MAXN];
vector<int> G[MAXN];
bool vis[MAXN];
int fa[MAXN], rt[MAXN];
long long ans;

void init(segmentTreeMgr &mgr)
{
    mgr.clear();
    for (int i = 1; i <= n; ++i)
    {
        vis[a[i].second] = false;
        fa[a[i].second] = a[i].second;
        rt[a[i].second] = 0;
        mgr.add(rt[a[i].second], a[i].first, 1);
    }
}

int findf(int x)
{
    return fa[x] == x ? x : fa[x] = findf(fa[x]);
}

void merge(segmentTreeMgr &mgr, int x, int y, long long val)
{
    auto fx = findf(x);
    auto fy = findf(y);
    if (mgr.query(rt[fx], 1, n) < mgr.query(rt[fy], 1, n))
    {
        swap(fx, fy);
    }
    vector<pair<int, int>> p;
    mgr.dump(rt[fy], p);
    for (auto &[i, j]: p)
    {
        ans += val * mgr.query(rt[fx], i - k, i + k) * j;
    }
    for (auto &[i, j]: p)
    {
        mgr.add(rt[fx], i, j);
    }
    mgr.remove(rt[fy]);
    fa[fy] = fx;
}

void go(segmentTreeMgr &mgr, const pair<int, int> &now, int op)
{
    vis[now.second] = true;
    for(auto&i:G[now.second])
    {
        if (vis[i])
        {
            merge(mgr, now.second, i, now.first * op);
        }
    }
}
int main()
{

    scanf("%d %d", &n, &k);
    segmentTreeMgr seg(M);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i].first);
        a[i].second = i;
    }
    for (int i = 1; i < n; ++i)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    sort(a + 1, a + 1 + n);
    init(seg);
    for (int i = 1; i <= n; ++i)
    {
        go(seg, a[i], 1);
    }
    init(seg);
    for (int i = n; i; --i)
    {
        go(seg, a[i], -1);
    }
    printf("%lld\n", ans << 1);
    return 0;
}


/*
3 0
2 1 1
1 2
1 3

3 1
2 1 1
1 2
1 3

 * */

时间复杂度： $\rm O(n\cdot logn \cdot logV)$ ，其中 $V$ 表示值域