树上的每个节点均有各自的重量和价值，除了容量限制外，还要求选择一个节点时，其父节点也要被选择，求最大价值。

时间复杂度：$O(nm^2)$（其中 $n$ 为树的大小，$m$ 为容量限制）。

优化

对于枚举到的每个节点，记录一下其子树大小。

$dp$ 状态转移时，枚举的个数是当前这个子树大小，对应儿子节点的子树的大小，最后更新子树大小。

相当于每次转移都是从节点枚举过的子树，将没有枚举的儿子合并进来。这个过程对应于枚举以这个点为 $lca$ 的所有点对，总体上它枚举了树上所有点对。

时间复杂度：$O(n^2)$。

马神牛逼！（破音

马神牛逼！（破音

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

ll qpow(ll x, ll n) {
    ll r = 1;
    while (n > 0) {
        if (n & 1) r = r * x % mod;
        x = x * x % mod; n >>= 1;
    }
    return r;
}
ll inv(ll x) { return qpow(x, mod - 2); }
ll rev[maxn << 2];
int init(int m) {
    int step = 0, n = 1;
    for (; n < m; n <<= 1) ++step;
    for (int i = 1; i < n; i++) 
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (step - 1));
    return n;  
}
void ntt(vector<ll>& a, int n, int op) {
    for (int i = 0; i < n; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int h = 2; h <= n; h <<= 1) {
        ll wn = qpow(3, (mod - 1) / h);
        if (op == -1) wn = inv(wn);
        for (int i = 0; i < n; i += h) {
            ll w = 1;
            for (int j = i; j < i + h / 2; j++) {
                ll u = a[j], t = a[j + h / 2] * w % mod;
                a[j] = (u + t) % mod;
                a[j + h / 2] = (u - t + mod) % mod;
                w = w * wn % mod;
            }
        }
    }
    if (op == -1) {
        ll rn = inv(n);
        for (int i = 0; i < n; i++) a[i] = a[i] * rn % mod;
    }
}

$div3$ 恢复信心失败。

A Two distinct points

B Divisors of Two Integers

给了一个多重集合，存放着两个正整数 $x$ 和 $y$ 的所有因子，让你恢复出这两个数字。

显然最大值是一个解，对其质因数分解，从多重集合中删除，得到剩下数字中的最大值为另外一个解。

C Nice Garland

给一个只包含字母 $RGB$ 的串，现在要求这个串 $s$ 满足

你可以修改一些位置使得上条件满足，求最小修改数和修改方案。

显然，这个串的前 $3$ 个位置只有 $6$ 种情况，后面部分一直重复这个前缀，枚举前缀即可。

D Diverse Garland

给一个只包含字母 $RGB$ 的串，现在要求这个串 $s$ 满足所有相邻位置字母不同。

你可以修改一些位置使得上条件满足，求最小修改数和修改方案。

考虑 $dp[i][3]$ 表示前 $i$ 个位置，最后一个为 $RGB$ 的最小修改数，跑一遍 $dp$，再倒着转移把方案构造出来。

菜鸡选手不会写倒着重构 $dp$。

E Array and Segments

给一个序列

现在有 $q$ 次询问，每次将区间 $[l,r]$ 所有位置都 $-1$，现在你需要从询问中选择一些执行，使得序列极差最大，即最大化 $\max a_i - \min a_i$。

对于一类求极差的问题，可以转化为枚举一个，快速计算另外一个。

因此，我们枚举最大值的位置，将所有不包含这个位置的线段全部执行，询问整个区间的最小值，这部分线段树更新和查询即可。

但是此时复杂度为 $O(nm\log n)$。

优化一下，我们可以用类似于双指针的思想，枚举每一个位置时，更新一些询问和撤销一些询问，因此每个询问最多被更新 $2$ 次。

时间复杂度 $O((n+m)\log n)$。

菜鸡选手并不知道极差的套路。

F MST Unification

给一个无向带权连通图，现在你可以将某些边权 $+1$ ，求最小的修改次数使得修改后的最小生成树唯一，且最小生成树权值不增加。

已经求出一棵最小生成树，当且仅当一些非树边的权值等于其对应树上路径的最大边权时，可以将路径上的最大边断掉换成这个非树边。

所以问题转化为快速求得树上一条路径的最大边权，在树上建一棵主席树即可。

菜鸡选手没有思维，只会无脑拍数据结构。

$C$ 卡主席树内存，是不是有点毒瘤啊？不会卡内存，自闭了啊？

下分大失败？

A Splitting into digits

输出 $n$ 个 $1$。

B Game with string

栈模拟。

第一次插人失败很难受啊，还好是小号啊？

C Grid game

一个 $4 \times 4$ 的方格图，往里面填 $1 \times 2$ 和 $2 \times 1$ 两种方块，放完后每一行，每一列填满的话就删除，要求填的时候不能无处可填，求一个方案。

考虑这样一种填法，竖着的都放在最左边，横着的放在右边，这样每进来 $2$ 个竖的都会被消掉，进来的是横的每 $4$ 个会消掉，不会产生冲突。

D Game with modulo

猜模数 $a$，每次询问两个数 $x$ 和 $y$，得到 $x \text{ mod } a$ 和 $y \text{ mod } a$ 的大小关系。

如果 $x > a$，那么 $ x \text{ mod } a < {1 \over 2}x$，因此可以先倍增求出 $a$ 的范围，在这个范围内二分即可。