F、我的心是冰冰的

根据树的特性，一定可以使用黑白染色把它分开，注意特判只有一个节点的情况即可。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
struct Node {
    ll val;
    int id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
};

const int N = 1e6 + 7;
ll n, m;
ll p[N];
void solve() {
    n = read();
    rep(i, 2, n) {
        int u = read(), v = read();
    }
    if (n == 1)    print(1);
    else print(2);
}

int main() {
    int T = read();    while (T--)
        solve();
    return 0;
}

B、比武招亲（上）

把题目转换到数轴上观察，很明显我们如果固定了序列的最大值已经最小值，那么它的贡献就是固定的，变化的只是方案数。所以我们可以枚举全部的最大最小值的差，去找寻方案数即可。

假设我们当前枚举的，我们选择的最大点是3，最小点是1，这样的话如果，显然需要花费2个去占领左右端点，那么接下来的方案数就是在1到3之间随便放入3个，求本质不同的方案数。这个求解我们使用隔板法。

我们有3个球，隔板分成3份，如果我们要求分出来的每一份都不能为空的话，我们就要在3个球中间的2个位置插入2个隔板。方案数是。现在我们允许有地方为空值，那就是增加需要分成份数那么多球，再去插入隔板，插入完毕之后把之前放进来的球直接拿走就是了。那么总的方案就是。

那么回到这个题，对于我们枚举的每个，显然最终答案贡献就是。

const int N = 1e6 + 7;
ll n, m;
ll jc[N], inv[N];

ll C(int n, int m) {//C(3,2)
    return jc[n] * inv[m] % MOD * inv[n - m] % MOD;
}

void solve() {
    jc[0] = 1;
    for (int i = 1; i < N; ++i)
        jc[i] = jc[i - 1] * i % MOD;
    inv[N - 1] = qpow(jc[N - 1], MOD - 2, MOD);
    for (int i = N - 2; i >= 0; --i)
        inv[i] = inv[i + 1] * (i + 1) % MOD;
    n = read(), m = read();
    if (n == 1 or m == 1) {
        print(0);
        return;
    }
    ll ans = 0;
    rep(i, 1, n - 1) {
        ans = (ans + C(i + m - 2, m - 2) * (n - i) % MOD * i % MOD) % MOD;
    }
    print(ans);
}

D、石子游戏

每次只能选择长度为的段全部加1，那么考虑差分处理。
我们思考，从前往后遍历原本的序列，那么如果第一个出现相邻前后不一致的位置就是我们要处理的点，我们分情况讨论。
如果，那么显然我们要把前面全部相同的个数全部慢慢变成，但是这样做的前提就是前面可以被整除。如果可以方案数累加，如果不行输出。
如果，那么我们就一定要把挨着的数变成相同，也就是把这一段增加，快速的使得区间全部数累加，我们就要使用差分处理了。只需要使得，同时我们还需要注意，我们差分的判断不能超过了原本序列长度，也就是如果我们时，说明已经超出了长度，后面不存在长度为的序列让你递增了，也就是无解的情况。

const int N = 1e6 + 7;
ll n, m;
ll a[N], b[N];

void solve() {
    n = read(), m = read();
    ms(b, 0);
    rep(i, 1, n)    a[i] = read();
    bool flag = 1;
    ll ans = 0;
    rep(i, 2, n) {
        b[i] += b[i - 1];
        a[i] += b[i];
        if (a[i] > a[i - 1]) {
            if ((i - 1) % m) {
                print(-1);
                return;
            }
            else {
                ans += (a[i] - a[i - 1]) * ((i - 1) / m);
            }
        }
        else if (a[i] != a[i - 1]) {
            if(i + m > n + 1){ // 赛中一直wa就在这里。。
                print(-1);
                return;
            }
            ans += a[i - 1] - a[i];
            b[i] += a[i - 1] - a[i];
            b[i + m] -= a[i - 1] - a[i];
            a[i] = a[i - 1];
        }
    }
    print(ans);
}
/*
3 2
2 1 3
3

4 2
1 2 2 2
-1

7 2
2 1 3 2 1 3 4
6

7 2
2 1 3 2 4 4 4
11
*/

A、美丽的路径

判断能不能到达使用并查集即可维护连通块信息。但是如果要找最大的这个答案应该怎么办？ 我们看样例，它是如何构造答案的，就是一直反复的走一条路，这样我们排序之后的答案中就会被两种数一直填充左右两边，那么我们填充的数可以改变答案的数有什么特点呢？