CCPC-Wannafly Winter Camp Day8 (Div1, onsite) 题解+代码（ABEG）

比赛链接：(Onsite) (Online mirror)

A. Aqours（13 通过，已补题）

其实就是一个挺简单的树上问题。。。当时没时间看这道题，血亏。。。但是需要注意，这道题输入量高达，最好使用快读，不然很可能被卡常数。

出题人题解：给出的点可以视为是按照 BFS 序给的，也就是说从浅到深给出。可以再给每个节点 u 维护一个 f_u 值， 表示离 u 最近的叶子节点到它的距离。所以每当扫到一个叶子节点，就可以暴力往根节点跳，边跳边更新 f 值，直到跳到一个已被其他叶子节 点跳到过的节点为止。 那么对于当前的叶子节点，离它最近的编号小于它的叶子节点到它的距离就是跳到这个终止节点的 f 值 +跳的步数。 在求完之后，还要从上述的终止节点沿着原路更新一下 f 值，因为可能当前叶子比较深但之前有比较浅 的叶子节点。 因为点是按从浅到深的顺序给出，所以一个节点的 f 值只会被最先跳到它的叶子节点赋值一次，也只会被更新一次，所以复杂度是 O(n) 的。

Status: 已补题（2019-01-29）

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 1; i <= n; ++i)
using namespace std;
typedef long long ll;const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)template<typename T> void read(T &x){x = 0; int f = 1; char ch = gc();while(!isdigit(ch) ) { if(ch == '-') f = -1; ch = gc();}while( isdigit(ch) ) {x = x * 10 + ch - 48; ch = gc();}x *= f;
}const int MAXN = 100200;
int fa[MAXN], n, f[MAXN], root = 1;
vector<int> G[MAXN], leaf;inline void link(int x, int y) {G[x].push_back(y);G[y].push_back(x);
}int main() {memset(f, -1, sizeof f);read(n);if(n == 1) { puts("1 -1"); return 0; }for(int i = 2; i <= n; ++i)read(fa[i]), link(i, fa[i]);for(int i = 2; i <= n; ++i) if(G[i].size() == 1u) leaf.push_back(i);for(auto v : leaf) {int p = v, cnt = -1;printf("%d ", v);while(p != root && f[p] == -1)f[p] = ++cnt, p = fa[p];if(p == root && f[p] == -1) {f[p] = ++cnt;puts("-1");} else {printf("%d\n", cnt + f[p] + 1);}f[p] = min(f[p], cnt + 1);int to = p, cur = cnt + f[p] + 1; p = fa[v];while(p != to) {f[p] = min(f[p], --cur);p = fa[p];}}return 0;
}

B. 玖凛两开花（34 通过，场上AC）

要求的是一个最小值的最大，很容易联想到二分。假设答案是x，则0, 1, ..., x - 1这些数一定要被匹配，显然有贪心结论：0, 1, ..., x - 1之间一定不能连边。那么把0, 1, ..., x - 1放在一边，x, x + 1, ..., n - 1放在另一边，跑最大匹配，这就是一个二分图匹配问题，可以用Dinic解决。复杂度