\(10+30+30+10=80\)，有挂惨了。

比赛链接：http://172.45.35.5/d/HEIGETWO/homework/66f4fec944f0ed11b057cca9
或 http://172.45.35.5/d/HEIGETWO/homework/66f4fec944f0ed11b057cca9

A - 智乃的差分

题意：

给定一个数列 \(a_n\)（\(0\le a_i\le 10^9\)），你可以重排这个数组，问是否存在一种排序方式，使得 \(a\) 的差分数组 \(d\) 中不出现 \(x\) 这个数，若可以，求输出方案。

思路：

考虑当 \(a\) 数组升序排序时，差分数组中都是正数，那么可以解决 \(x\) 为负数的情况，所以我们考虑按照 \(x\) 的符号分类讨论。

\(x<0\) 讨论完了，下面讨论 \(x>0\) 或 \(x=0\)。

当 \(x>0\) 时，考虑降序排序数组 \(a\)，那么 \(d\) 中的 \(2\) 到 \(n\) 个元素全是负数，但是第一个数可能等于 \(x\)，考虑将后面的一个属交换到前面，我们要保证这个数不等于 \(x\) 且不等于 \(0\)，若没有这样的数就输出 no。

当 \(x=0\) 时，就是要满足重排后的数组的第一个元素不为 \(0\) 且没有相邻的相同元素，这是一个很经典的问题，我们每次找到出现次数最多的元素，若这个数与前面的数不相同，那么就使用这个数，否则使用出现次数次大的元素，将这些数放在另一个答案数组中并在原数组中删除。由于出现次数时持续变化的，所以需要用优先队列维护。

代码：

#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 1e5 + 5;

int T, n, m, x, a[kMaxN], b[kMaxN], p, tot, f;
map<int, int> mp;

int main() {
  freopen("difference.in", "r", stdin);
  freopen("difference.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  for (cin >> T; T; T--) {
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    if (x < 0) {
      sort(a + 1, a + 1 + n);
      cout << "yes\n";
      for (int i = 1; i <= n; i++) {
        cout << a[i] << ' ';
      }
      cout << '\n';
    } else if (x > 0) {
      sort(a + 1, a + 1 + n, greater<int>());
      if (x != a[1]) {
        cout << "yes\n";
        for (int i = 1; i <= n; i++) {
          cout << a[i] << ' ';
        }
        cout << '\n';
      } else {
        p = -1;
        for (int i = 1; i <= n; i++) {
          a[i] != a[1] && a[i] && (p = i);
        }
        if (p == -1) {
          cout << "no\n";
        } else {
          cout << "yes\n" << a[p] << ' ';
          for (int i = 1; i <= n; i++) {
            i != p && (cout << a[i] << ' ');
          }
          cout << '\n';
        }
      }
    } else {
      mp.clear(), f = 0;
      priority_queue<pair<int, int>> q;
      for (int i = 1; i <= n; i++) {
        mp[a[i]]++, b[i] = 0;
      }
      for (pair<int, int> i : mp) {
        q.push({i.second, i.first});
      }
      for (int i = 1; i <= n; i++) {
        pair<int, int> now = q.top();
        q.pop();
        if (now.second == b[i - 1]) {
          if (q.size()) {
            pair<int, int> tmp = q.top();
            q.pop(), b[i] = tmp.second, q.push(now);
            if (--tmp.first) {
              q.push(tmp);
            }
          } else {
            f = 1;
            break;
          }
        } else {
          b[i] = now.second;
          if (--now.first) {
            q.push(now);
          }
        }
      }
      if (!f) {
        cout << "yes\n";
        for (int i = 1; i <= n; i++) {
          cout << b[i] << ' ';
        }
        cout << '\n';
      } else {
        cout << "no\n";
      }
    }
  }
  return 0;
}

B - 牛牛的旅行

题意：

给定一颗 \(n\) 个节点的树，每个点有一个点权，定义一条简单路径的权值为路径中点权的最大值减去路径的长度，求树上所有长度不为 \(0\) 的简单路径的权值和模 \(10^9+7\) 的值。

思路：

首先可以将两种操作分开，计算所有路径的长度和可以用换根 dp 求解，很板，不做讨论，下面只讲如何求解所有路径经过点权的最大值的和。