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、比武招亲（上）

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

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

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

那么回到这个题，对于我们枚举的每个 $d$ ，显然最终答案贡献就是 $\sum\limits_{d=1}^{d=n-1}d*(n-d)*C^{m-2}_{d+m-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、石子游戏

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

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、美丽的路径

判断能不能到达使用并查集即可维护连通块信息。但是如果要找最大的这个答案应该怎么办？
我们看样例，它是如何构造答案的，就是一直反复的走一条路，这样我们排序之后的答案中就会被两种数一直填充左右两边，那么我们填充的数可以改变答案的数有什么特点呢？
我们看，我们直接从 $s\to t$ 可以得到一组序列，我们对这组序列排序之后，我们走重复的路时，一定是添加一次大的在右边，一次小的在左边，我们这样做的情况下真的可以改变原先的排列嘛？仔细思考，我们就可以得到永远不可能通过走路使得路径中较大的一端成为中点。我

2021牛客寒假算法基础集训营5

F、我的心是冰冰的

B、比武招亲（上）

D、石子游戏

A、美丽的路径