预期：没有预期，因为是 IOI 赛制。
实际：\(100+100+65+100+50+0=415\)。
排名：\(rk55/148\)。
A - 树链上的连续段：
题意：
给定一个 \(n\) 个点的树，每个点被赋值为 \(0/1\)，其中有 \(k\) 个 \(1\)，定义 \(f(x,y)\) 表示 \(x\) 到 \(y\) 的简单路径上的所有点的点权顺序写下来的连续段数量。你需要给 \(n\) 个点赋权，最小化 \(f(x,y)\) 的最大值。
思路：
首先注意到答案肯定不超过 \(3\)，因为你给一个连通块赋值为 \(1\)，那么肯定有 \(\max f(x,y)\le 3\)，所以我们只需要判断答案为 \(1,2\) 的情况即可。
答案为 \(1\) 的充要条件显然是 \(k=0,n\)，构造方案就是全 \(0\) 或全 \(1\)。
答案为 \(2\) 的充要条件需要手玩一下，我们发现如果一颗子树（根不固定）的大小刚好等于 \(k\)，那么答案显然是 \(2\)，这其实就是充要条件，然后直接枚举根算子树大小就可以了。
答案为 \(3\) 直接构造一个连通块即可。
代码：
#include <bits/stdc++.h>using namespace std;const int kMaxN = 2005;int T, n, k, deg[kMaxN], siz[kMaxN], dep[kMaxN];
bool col[kMaxN], flag;
vector<int> g[kMaxN];void Clear() {flag = 0;for (int i = 1; i <= n; i++) {g[i].clear(), col[i] = deg[i] = 0;}
}void Dfs(int u, int fa) {siz[u] = 1, dep[u] = dep[fa] + 1;for (int v : g[u]) {if (v != fa) {Dfs(v, u);siz[u] += siz[v];}}
}void Dfs1(int u) {col[u] = 1;for (int v : g[u]) {if (dep[v] > dep[u]) {Dfs1(v);}}
}void Dfs2(int u, int fa) {if (flag) return;col[u] = 1, k--;if (k == 0) {flag = 1;return;}for (int v : g[u]) {if (flag) return;if (v != fa) Dfs2(v, u);if (flag) return;}
}int main() {ios::sync_with_stdio(0), cin.tie(0);for (cin >> T; T; T--, Clear()) {cin >> n >> k;for (int i = 1, u, v; i < n; i++) {cin >> u >> v;g[u].push_back(v), g[v].push_back(u);deg[u]++, deg[v]++;}if (k == 0) {cout << "1\n";for (int i = 1; i <= n; i++) {cout << "0 ";}cout << '\n';} else if (k == n) {cout << "1\n";for (int i = 1; i <= n; i++) {cout << "1 ";}cout << '\n';} else {pair<int, int> p = {-1, -1};for (int rt = 1; rt <= n; rt++) {Dfs(rt, 0);for (int i = 1; i <= n; i++) {if (siz[i] == k) {p = {rt, i};break;}}if (~p.first) break;}if (~p.first) {cout << "2\n";Dfs1(p.second);} else {cout << "3\n";Dfs2(1, 0);}for (int i = 1; i <= n; i++) {cout << col[i] << ' ';}cout << '\n';}}return 0;
}