九省联考 2018

一双木棋

发现状态数很少，直接搜即可。

IIIDX

不难发现这个偏序关系形成了一棵树。

本来以为直接贪心即可，即把 \(a\) 排序，然后 dfs / bfs 一遍直接安排权值，类似于这样：

void dfs1(int u) {
    sz[u] = 1;
    for (int v : e[u]) dfs1(v), sz[u] += sz[v];
}

void dfs2(int u) {
    int p = ans[u] + sz[u] - 1;
    for (int v : e[u]) ans[v] = p - sz[v] + 1, dfs2(v), p -= sz[v];
}

不出我所料，这份简单的代码没有过，被这组数据叉掉了：

2 2.0
1 1 1 2

发现这样贪心得到的结果是 1 1 1 2；而正确答案是 1 1 2 1。发现我们要做的实际上是依次从 \(1 \sim n\) 安排每一个位置上的数，安排的时候要判断剩下的所有条件能否被满足，条件即要给一些点预留一些数量的数，那么使用线段树维护即可。时间复杂度 \(\mathcal{O}(n \log n)\)。记得搜到一个点时消除其对父亲的影响。

不过送 \(55\) 分也够高了。

林克卡特树

wqs 二分，凸性不会证。

考虑把新边的权值改为 \(c\)，然后做 DP。贪心好像不太行，于是考虑 DP：问题等价于求出 \(k + 1\) 条链，使得它们的权值和最大。

考虑二分给每一条链加上一个额外权值 \(c\)。我们可以设 \(f_{u, 0 / 1 / 2}\) 表示以 \(u\) 为根的子树内 \(u\) 未被选择 / 是一条链的端点 / 是一条链的中间部分时的答案，并同时记录相应的链数量即可。

时间复杂度 \(\mathcal{O}(n \log V)\)。