CSP-S模拟赛总结

记录一下 CSP-S 2025 到来之前，我打过的模拟赛们。

核桃编程模拟赛

过程记录

这是我打的第一场对标 CSP-S 难度的 OI 赛制比赛，并且我全程使用的 NOI Linux 2.0。
整场下来的经过：

• 没有中文输入法，没法注释做题了，用草稿纸做题好不习惯。
• 使用的 Sublime 写的代码，挺好用哈。
• 四个题全都看了一遍，分析出了总共 100 分左右的暴力分，然后开始打，这个时候大概过去了 25 分钟。
• 直接开写第一题的第二档暴力，咋感觉不太好写。。。算了还是写一下最暴力的做法吧。
• 第二题暴力打完，哎还有一个性质极为简单，直接输出答案即可。
• 第三题打一个最暴力的做法，然后发现有两个性质非常好做，顺手写了。
• 第四题写了个最暴力的做法。
• 咋写了这么多不同的部分分代码？3 小时输出了快 600 行代码。
• 为了测不同的部分分，开始疯狂改 solve() 函数里的分派逻辑，改得乱七八糟。
• 我的代码疑似变得非常乱了，不同部分分之间的数据结构以及函数堆在了一起难以区分。看起来还是学一下咋用 namespace 比较好，每个部分分写到一个 namespace 里面。
• 还剩 1 小时，我是写 T1 另外 40 分的部分分，还是写 T2 20 分部分分？我 T1 40 分的代码已经有了，要不继续写 T1 吧。
• 好难写的 T1，终于写好了，写个拍子试一下。
• 对拍挂了，怎么看起来是暴力挂了？哎真的是暴力挂了吗？哦原来还是部分分写错了。
• 手动测一下，SF 了，看来得二分调试法了。
• 全程 cout 调试，然后发现删调试好麻烦啊，ctrl + f 到处看防止漏删爆零！后来想到定义一个 LOCAL_DEBUG 宏，把调试语句都用这个宏包起来，本地测试时带上这个宏，提交时评测机上没有这个宏。
• 还剩 10 分钟，感觉调不出来了，不改任何逻辑了，看一下每个题的 solve() 函数，然后直接交。
• 我超忘了加文件读写了，还好 OJ 有提示，后来想起来可以加 LOCAL_TEST 宏，如果没有定义（#ifndef LOCAL_TEST）这个宏，则条件编译文件读写代码。
• 最后由于全都打的暴力，所以甚至大样例都没有用上，后面几个题也约等于没有做测试，理论上最高可能得分 125 分，但是感觉可能会挂分。
• OI 赛制和其他赛制差别太大了，要考虑的其他因素好多，非智力精力消耗很大，感觉因为这些原因少写 30 分的部分分，一直在打打打打暴力，没有做很多深入的思考。

经验教训

不要预先假定你的 T1 能拿满分，甚至不要预先假定能拿 50 分。最开始就从最基本的暴力开始打就好，反正最后也是要对拍的。

一等奖分数线并不高，稳妥起见，建议永远先打更容易写的部分分。这次比赛时，最后一个多小时就遇到了 40 分难写和 10 分相对好写的部分分之间的抉择，决策时考虑到 40 分的部分分的代码最最开始已经写过一些了，感觉更容易快速写完，于是就选的 40 分的，结果最后对拍发现寄了，且没调出来。

大样例只能测正解或者接近正解的代码，并不能测自己写的暴力代码。如果某道题自己只会写一档暴力，则必须要多测试。对于特殊性质的部分分，如果不好自动化批量对拍，则一定要多手造几组测一下。

平时做题写代码都是写正解，但是考场上写的大部分代码都是暴力、拍子之类的，并且代码量明显比平时要大，这一定程度上反应了训练和比赛时写的代码存在 gap。平时各种正解打得很爽，但比赛时未必就能把部分分写好，部分分也是要专门练习的。

一种尝试性的 OI 赛制代码架构，或许可以在写部分分时代码更干净一些：

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 2e5 + 10;

/*
全局数据区，主要存储原始输入数据
对于每个 subtask，它可能还会用到其他的数据结构
比如哈希表，比如 vis 数组，比如记录暴搜过程中结果的 res 等
这些数据放在对应的 namespace 里面
不同的 subtask 需要相同的其他数据结构，除非是所有 namespace 都需要这个数据结构
否则最好也是各自在自己的 namespace 中开出来
*/
int n, x, y, m, a[N], b[N], c[N];

/*
每个 subtask 写一个 namespace，可以根据测试点编号给 namespace 命名
每个 subtask 的 solve 函数运行时，需要先做数据初始化，然后再执行逻辑
*/
namespace subtask_1_8 {
    int vis[N], res;

    void solve() {
        /*
        调试时，使用条件编译技术，将调试语句用 ifdef 和 endif 包裹起来
        本地调试时，加上 -D LOCAL_DEBUG 宏，即可输出调试信息
        提交后，由于评测环境中没有这个宏，所以不会输出调试信息
        这样写相比于用 cerr 的好处是，在评测时不会带来输出的开销，不会因为调试语句超时
        */
        #ifdef LOCAL_DEBUG
        cout << "some current state" << "\n";
        #endif
    }
};

namespace subtask_9_13 {
    map<int, int> cnt;

    void solve() {

    }
};

namespace subtask_14_20 {
    int vis[N];

    void solve() {

    }
};

// 一些对输入数据分析的函数，用于判断到底分派给哪个 subtask 执行
bool all_equal() {
    return true;
}

// 实现 subtask 的分发逻辑
void solve() {
    /*
    进行必要的读入，“必要”指的是足以判断出输入数据的特征
    半数情况下，通过 n 的大小即可分发
    另外半数情况，可能需要读入更多的数据，通过一些算法去判断是否有某种性质
    这些算法可以实现在对应的 subtask namespace 里面，也可以写函数
    但不建议直接在分派任务的 solve 里面写具体的检查逻辑
    */
    cin >> n >> x >> y >> m;
    if (n <= 100) {
        subtask_1_8::solve();
    } else {
        for (int i = 1; i <= m; i++) {
            cin >> a[i] >> b[i] >> c[i];
        }

        if (all_equal()) {
            subtask_9_13::solve();
        } else {
            subtask_14_20::solve();
        }
    }
}

int main() {
    /*
    本地测试时定义宏 LOCAL_TEST，用于禁用文件读写
    提交后由于编译时没有这个宏，所以文件读写会被打开
    */
    #ifndef LOCAL_TEST
    freopen("shuffle.in", "r", stdin);
    freopen("shuffle.out", "w", stdout);
    #endif

    ios::sync_with_stdio(false);
    cin.tie(0);

    // 用于应对多测
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

本地运行时，可以使用 g++ a.cpp -o a -Wall -static -std=c++14 -O2 -D LOCAL_TEST 来编译。

本地调试时，可以使用 g++ a.cpp -o a -Wall -static -std=c++14 -O2 -DLOCAL_TEST -DLOCAL_DEBUG 来编译。

CSP-S 2022自行模拟

单独做的题目，模拟仅有一次提交机会，且需要在一定时间限制内提交。

T1

• 首先很容易想到 $O(n^4)$ 的做法去解决 $k = 0$ 的情况，按照经过顺序枚举四个点，判断是否连边即可。很快实现出来了，可以通过 1-3 的部分分。
• 接下来，发现其实可以枚举一条边 + 第一个点 + 最后一个点，这样复杂度降到了 $O(n^2m)$，可以通过 9-11 的部分分。
• 对拍，发现输出一样，没有问题（真的吗）。
• 接下来决策是做 $k = 0$ 但 $n$ 比较大的情况，还是做 $n$ 比较小但 $k$ 不为 0 的情况。思考了一下，发现 $k \ne 0$ 时，假如 $n$ 比较小，似乎可以考虑预处理一下从 $i$ 走到 $j$ 不超过 $k$ 步是否可行，预处理出来之后再枚举到底经过哪四个点，判断一下不超过 $k$ 个中间点能否走到就好了。
• 写完测了一下发现很不对，然后发现 $k$ 忘了读入了！这居然都能过 $k = 0$ 的样例！太弱了。改了之后又发现实际上应该是能走 $k + 1$ 步，又做了一些修改。
• 测大样例，发现结果不对，然后发现大样例数据范围爆了数组，所以要改一下数组大小再测，然后发现对了。
• 自信提交，预期 55 分，实际得分 55 分！至此，用时 1 小时 20 分钟。

赛时实现的代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 3e3 + 10;

/*

*/

LL n, m, k, a[N];
vector<vector<int>> e(N);

namespace subtask_1_3 {
	int w[N][N];

	void solve() {
		for (int i = 1; i <= n; i++) {
			for (auto u : e[i]) {
				w[u][i] = 1;
				w[i][u] = 1;
			}
		}

		LL res = 0;
		for (auto u1 : e[1]) {
			for (auto u2 : e[1]) {
				if (u1 != u2) {
					for (auto u3 : e[u1]) {
						if (u1 != u3 && u2 != u3) {
							for (auto u4 : e[u2]) {
								if (u3 != u4 && u1 != u4 && u2 != u4) {
									if (w[u3][u4] == 1) {
										res = max(res, a[u1] + a[u2] + a[u3] + a[u4]);
									}
								}
							}
						}
					}
				}
			}
		}
		cout << res << endl;
	}
};

namespace subtask_9_11 {
	int w[N][N];

	void solve() {
		for (int i = 1; i <= n; i++) {
			for (auto u : e[i]) {
				w[u][i] = 1;
				w[i][u] = 1;
			}
		}

		LL res = 0;
		for (int i = 2; i <= n; i++) {
			for (int j = 0; j < (int)e[i].size(); j++) {
				int u2 = i, u3 = e[i][j];
				for (int u1 = 1; u1 <= n; u1++) {
					if (u1 == u2 || u1 == u3) {
						continue;
					}
					for (int u4 = 1; u4 <= n; u4++) {
						if (u4 == u1 || u4 == u2 || u4 == u3) {
							continue;
						}

						if (w[1][u1] && w[u1][u2] && w[u2][u3] && w[u3][u4] && w[u4][1]) {
							res = max(res, a[u1] + a[u2] + a[u3] + a[u4]);
						}
					}
				}
			}
		}
		cout << res << endl;
	}
};

namespace subtask_4_8 {
	/*
	dp[cnt][i][j]: from i to j, walk <= cnt steps, can arrive?
	dp[cnt][i][j] ||= dp[cnt - 1][i][u], if edge (u, j) exists
	O(n^3 * k)
	
	meiju u1, u2, u3, u4
	if dp[k][1][u1], dp[k][u1][u2], dp[k][u2][u3], ... all true
	we can add u1 u2 u3 u4
	O(n^4)
	*/

	LL dp[102][30][30];
	int w[N][N];

	void solve() {
		#ifdef LOCAL_DEBUG
		cout << "debug start" << "\n";
		#endif

		for (int i = 1; i <= n; i++) {
			for (auto u : e[i]) {
				w[u][i] = 1;
				w[i][u] = 1;
			}
		}

		for (int i = 1; i <= n; i++) {
			dp[0][i][i] = 1;
		}

		for (int cnt = 1; cnt <= k + 1; cnt++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					dp[cnt][i][j] = dp[cnt - 1][i][j];
					for (int u = 1; u <= n; u++) {
						if (w[u][j] == 1) {
							dp[cnt][i][j] |= dp[cnt - 1][i][u];
						}
					}
				}
			}
		}

		#ifdef LOCAL_DEBUG
		cout << dp[1][5][8] << " " << dp[2][5][8] << "\n";
		#endif

		LL res = 0;
		for (int u = 2; u <= n; u++) {
			for (int v = 2; v <= n; v++) {
				if (u == v) continue;
				for (int i = 2; i <= n; i++) {
					if (u == i || v == i) continue;
					for (int j = 2; j <= n; j++) {
						if (u == j || v == j || i == j) continue;

						if (dp[k + 1][1][u] && dp[k + 1][u][v] && dp[k + 1][v][i] && dp[k + 1][i][j] && dp[k + 1][j][1]) {
							res = max(res, a[u] + a[v] + a[i] + a[j]);
							
							#ifdef LOCAL_DEBUG
							if (res == a[u] + a[v] + a[i] + a[j]) {
								cout << "find " << u << " " << v << " " << i << " " << j << "\n";
								cout << "value: " << res << "\n";
							}
							#endif
						}
					}
				}
			}
		}
		cout << res << endl;
	}
};

void test() {

}

void solve() {
	cin >> n >> m >> k;
	for (int i = 2; i <= n; i++) {
		cin >> a[i];
	}

	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		e[a].push_back(b);
		e[b].push_back(a);
	}

	if (n <= 10 && k == 0) {
		subtask_1_3::solve();
	} else if (n <= 300 && k == 0) {
		subtask_9_11::solve();
	} else {
		subtask_4_8::solve();
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int T = 1;
	// cin >> T;
	while (T--) {
		solve();
	}

	return 0;
}

光这道题上来就写了快 200 行代码了，我 4 小时输出 600 行代码就很麻了，感觉上来就消耗了很多码力。我觉得以后上来不能写太复杂的逻辑，要循序渐进，慢慢进入状态。

T2

• 首先发现 200 的数据范围可以把矩阵建出来直接暴力，写了。
• 然后发现 1000 的数据范围下，可以用 ST 表去搞每行的区间 min，写了。
• 接着，发现在性质 1 下，其实就是 max(a[l1...r1]) * min(b[l2...r2])，写了，拍的时候好像是没问题，但是提交上去挂了，原因是因为我**复制了第二档部分分的 ST 表，但是范围没改得足够大！**所以导致了挂分。
• 最后发现正解无非也就是分类讨论，但是没有写。
• 做这道题时，发现每次写完一档暴力分，发现下一档也会做了。经过分析，我觉得是暴力分写得太着急了，其实完全可以再多分析 5 分钟，这样似乎能少写一些代码。
• 总结出了一些经验：
  • 最暴力的暴力当然是要写的（一般来说也很好写），因为要对拍；后边的暴力分最好写得别那么着急，分析出一档暴力分之后，可以再往后思考一点，看看能不能想出来下一档，如果想出来了，就有可能可以少写一档暴力，给后边的题留一些时间。没想出来也没关系，得分更稳一些。
  • 复制代码很有可能导致错误，你总可能有些地方会忘了改！
  • 对拍后，还要对 MLE 和 RE 做最终的检查！

赛时代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
const int M = 1010;

/*

*/

typedef long long LL;

LL n, m, q, a[N], b[N];

namespace subtask_1_to_5 {
	/*
	create matrix
	count row, count col, find min
	x choose min max
	O(nmq)
	*/

	LL grid[210][210];

	void solve() {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				grid[i][j] = a[i] * b[j];
			}
		}

		while (q--) {
			int l[3], r[3];
			cin >> l[1] >> r[1] >> l[2] >> r[2];
			LL mx = -2e18;
			for (int i = l[1]; i <= r[1]; i++) {
				LL row_min = 2e18;
				for (int j = l[2]; j <= r[2]; j++) {
					row_min = min(row_min, grid[i][j]);
				}
				mx = max(mx, row_min);
			}
			cout << mx << "\n";
		}
	}
};

namespace subtask_6_to_12 {
	/*
	prepare every row's st_min
	O(nq)
	*/

	struct ST {
		LL st[12][M], lg[M], sz;

		void init(int _sz, LL a[]) {
			sz =_sz;
			for (int i = 2; i < M; i++) {
				lg[i] = lg[i / 2] + 1;
			}

			for (int i = 1; i <= sz; i++) {
				st[0][i] = a[i];
			}

			for (int j = 1; j < 12; j++) {
				for (int i = 1; i + (1 << j) - 1 <= sz; i++) {
					st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
				}
			}
		}

		LL query(LL l, LL r) {
			LL k = lg[r - l + 1];
			return min(st[k][l], st[k][r - (1 << k) + 1]);
		}
	};


	LL grid[M][M];
	ST st[M];

	void solve() {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				grid[i][j] = a[i] * b[j];
			}
		}

		for (int i = 1; i <= n; i++) {
			st[i].init(m, grid[i]);
		}

		while (q--) {
			int l[3], r[3];
			cin >> l[1] >> r[1] >> l[2] >> r[2];
			LL mx = -2e18;
			for (int i = l[1]; i <= r[1]; i++) {
				mx = max(mx, st[i].query(l[2], r[2]));
			}
			cout << mx << "\n";
		}
	}
};

namespace subtask_13_to_15 {
	/*
	if a[i], b[i] > 0, grid[i][j] = a[i] * b[j]
	for query l1, r1, l2, r2
	iterate i from l1 to r1
	find min b[l2...r2], a[i] * min(b[l2...r2]) 
	actually, we need to find max a[i]
	ans is max(a[l1...r1]) * min(b[l2...r2])
	*/

	struct ST_min {
		LL st[19][N], lg[N], sz;

		void init(int _sz, LL a[]) {
			sz =_sz;
			for (int i = 2; i < N; i++) {
				lg[i] = lg[i / 2] + 1;
			}

			for (int i = 1; i <= sz; i++) {
				st[0][i] = a[i];
			}

			for (int j = 1; j < 19; j++) {
				for (int i = 1; i + (1 << j) - 1 <= sz; i++) {
					st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
				}
			}
		}

		LL query(LL l, LL r) {
			LL k = lg[r - l + 1];
			return min(st[k][l], st[k][r - (1 << k) + 1]);
		}
	};

	struct ST_max {
        // 最开始复制过来的时候 12 忘了改成 19 了，导致暴毙了 15 分部分分
		LL st[19][N], lg[N], sz;

		void init(int _sz, LL a[]) {
			sz =_sz;
			for (int i = 2; i < N; i++) {
				lg[i] = lg[i / 2] + 1;
			}

			for (int i = 1; i <= sz; i++) {
				st[0][i] = a[i];
			}

			for (int j = 1; j < 19; j++) {
				for (int i = 1; i + (1 << j) - 1 <= sz; i++) {
					st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
				}
			}
		}

		LL query(LL l, LL r) {
			LL k = lg[r - l + 1];
			return max(st[k][l], st[k][r - (1 << k) + 1]);
		}
	};

	ST_min mn;
	ST_max mx;

	void solve() {
		mn.init(m, b);
		mx.init(n, a);

		while (q--) {
			int l1, r1, l2, r2;
			cin >> l1 >> r1 >> l2 >> r2;
			cout << mx.query(l1, r1) * mn.query(l2, r2) << "\n";
		}
	}
};

void solve() {
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> b[i];
	}


	if (n <= 200 && m <= 200 && q <= 200) {
		subtask_1_to_5::solve();
	} else if (n <= 1000 && m <= 1000 && q <= 1000) {
		subtask_6_to_12::solve();
	} else {
        subtask_13_to_15::solve();
    }
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int T = 1;
	// cin >> T;
	while (T--) {
		solve();
	}

	return 0;
}

T3

还剩下 1.5 小时做 T3 T4

这题题面太长太逆天了，图论题，读了 5 分钟没读明白，就跳过了，到最后也没时间做了。赛后看有人说全输出 NO 有 45 分？？？这可是多测题啊 bro。。。数据这么水的吗？看起来以后图论题不会写的话一定要瞎输出一点东西，这种题的数据很容易水掉。

赛后尝试做一下：

• 仔细读题，发现其实并不复杂，他就是问一个图里是否所有点出度为 1，且所有点都能走到一个环里。
• 所有点出度为 1 时，是个内向基环树，本来每个点就能走到环里。
• 所以只需要判这个事情就好了，直接爽拿 40 分。

赛后模拟代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

/*

*/

int n, m, q;

namespace subtask_1_to_3 {

	const int M = 12;

	int origin_w[M][M], w[M][M];
	int vis[M];

	bool dfs(int u) {
		vis[u] = 1;
		bool res = false;
		for (int v = 1; v <= n; v++) {
			if (w[u][v]) {
				if (vis[v]) {
					return true;
				}
				res |= dfs(v);
			}
		}
		return res;
	}

	bool check() {
		for (int i = 1; i <= n; i++) {
			int cnt = 0;
			for (int j = 1; j <= n; j++) {
				cnt += w[i][j];
			}

			if (cnt != 1) {
				return false;
			}

			memset(vis, 0, sizeof vis);
			if (!dfs(i)) {
				return false;
			}
		}
		return true;
	}


	void solve() {
		for (int i = 1; i <= m; i++) {
			int u, v;
			cin >> u >> v;
			w[u][v] = 1;
			origin_w[u][v] = 1;
		}

		cin >> q;
		while (q--) {
			int t, u, v;
			cin >> t;
			if (t == 1) {
				cin >> u >> v;
				w[u][v] = 0;
			} else if (t == 2) {
				cin >> u;
				for (int v = 1; v <= n; v++) {
					w[v][u] = 0;
				}
			} else if (t == 3) {
				cin >> u >> v;
				w[u][v] = 1;
			} else {
				cin >> u;
				for (int v = 1; v <= n; v++) {
					if (origin_w[v][u]) {
						w[v][u] = 1;
					}
				}
			}

			if (check()) {
				cout << "YES\n";
			} else {
				cout << "NO\n";
			}
		}
	}	
};

namespace subtask_4_to_8 {
	/*
	when every node has one out edge, the graph will be ji huan shu
	we just need to check if all the nodes are in loop, use O(n) time
	*/

	const int M = 1010;

	vector<set<int>> e(M);
	int origin_w[M][M], w[M][M], d[M];

	bool check() {
		for (int i = 1; i <= n; i++) {
			if (e[i].size() != 1) {
				return false;
			}
		}

		return true;
	}

	void solve() {
		for (int i = 1; i <= m; i++) {
			int u, v;
			cin >> u >> v;
			origin_w[u][v] = 1;
			w[u][v] = 1;
			e[u].insert(v);
		}

		cin >> q;
		while (q--) {
			int t, u, v;
			cin >> t;
			if (t == 1) {
				cin >> u >> v;
				e[u].erase(v);
				w[u][v] = 0;
			} else if (t == 2) {
				cin >> u;
				for (int v = 1; v <= n; v++) {
					if (w[v][u] == 1) {
						w[v][u] = 0;
						e[v].erase(u);
					}
				}
			} else if (t == 3) {
				cin >> u >> v;
				w[u][v] = 1;
				e[u].insert(v);
			} else {
				cin >> u;
				for (int v = 1; v <= n; v++) {
					if (origin_w[v][u] && !w[v][u]) {
						w[v][u] = 1;
						e[v].insert(u);
					}
				}
			}

			if (check()) {
				cout << "YES\n";
			} else {
				cout << "NO\n";
			}
		}
	}
};


void solve() {
	cin >> n >> m;
	if (n <= 10) {
		subtask_1_to_3::solve();
	} else {
		subtask_4_to_8::solve();
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int T = 1;
	// cin >> T;
	while (T--) {
		solve();
	}

	return 0;
}

T4

• 首先疑似发现了一个做法，是直接找树上从 s 到 t 的简单路径，然后用一个 DP 去求解最小花费。由于 k <= 3，所以总的时间复杂度 O(nqk)，可以跑 2000 的情况，预期这个做法能拿 44 分，花了一些时间写出来了。这时我有点疑惑为啥 k <= 3 而不是更大。
• 测试，发现普通用例都过了，两个大样例中有一个过了，有一个没过。具体来说，很大的那个居然过了，一个比较小的没过。我 debug 了 20 多分钟，意识到 k = 3 时不一定走简单路径，所以这个做法是错误的！只能解决 k <= 2 且 n 较小的情况，实际上只能拿 24 分。如果没有这个大样例的话，我很难发现自己是假做法。
• 由于我知道 k = 1 的情况如何做 n = 2e5 了，即直接使用 LCA + 树上前缀和，所以我去写了这个做法，然后写了个对拍，发现挂了。输出调试之后，发现是树上前缀和搞错了，改了之后拍了 1000 组数据没问题，这个做法预期能拿 8 分。
• 到这里只剩下 10 分钟的时间了，没时间搞其他题了，于是直接提交，果然拿到了总共 32 分。

赛时代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

typedef long long LL;

/*
D looks easier than C?
*/

int n, q, k;
LL v[N];
vector<vector<int>> e(N);

namespace subtask_1_to_11 {
	/*
	find lca, find all nodes in path
	use dp to calculate ans
	dp[i]: min cost to node i
	dp[i] = min(dp[j]) + v[i], if i - j <= k
	k <= 3, so the complexity is O(q * n * k)

	transmit 2 is wrong, but 3 is correct?
	fuck, k = 3 means we can go another node! maybe better

	*/

	const int M = 2010;
	int d[M], f[M];

	void calculate_depth(int u, int fa, int depth) {
		d[u] = depth;
		f[u] = fa;
		for (auto v : e[u]) {
			if (v != fa) {
				calculate_depth(v, u, depth + 1);
			}
		}
	}	

	void get_nodes(int s, int t, vector<int> &nodes) {
		vector<int> n1, n2;
		if (d[s] < d[t]) {
			swap(s, t);
		}
		while (d[s] > d[t]) {
			n1.push_back(s);
			s = f[s];
		}
		if (s == t) {
			n1.push_back(s);
			for (auto v : n1) {
				nodes.push_back(v);
			}
			return;
		} 

		while (s != t) {
			n1.push_back(s);
			n2.push_back(t);
			s = f[s];
			t = f[t];
		}

		n1.push_back(s);
		reverse(n2.begin(), n2.end());
		for (auto v : n1) {
			nodes.push_back(v);
		}
		for (auto v : n2) {
			nodes.push_back(v);
		}
	}

	void print(vector<int> &nodes) {
		for (auto v : nodes) {
			cout << v << " ";
		}
		cout << "\n";
	}

	void calculate_min_cost(vector<int> &nodes) {
		LL inf = 1e18;
		int cnt = nodes.size();
		vector<LL> dp(cnt + 1, inf);
		dp[0] = v[nodes[0]];
		for (int i = 1; i < cnt; i++) {
			for (int j = i - 1; j >= 0 && i - j <= k; j--) {
				dp[i] = min(dp[i], dp[j] + v[nodes[i]]);
			}
		}
		cout << dp[cnt - 1] << "\n";
	}

	void solve() {
		calculate_depth(1, 0, 0);

		while (q--) {
			int s, t;
			cin >> s >> t;
			#ifdef LOCAL_DEBUG
			cout << "query " << s << " " << t << "\n";
			#endif
			vector<int> nodes;
			get_nodes(s, t, nodes);
			#ifdef LOCAL_DEBUG
			print(nodes);
			#endif
			calculate_min_cost(nodes);
		}
	}
};

namespace subtask_12_to_13 {
	/*

	*/

	int fa[N][20], d[N], lg[N];
	LL s[N];

	void pre(int u, int f, int depth) {
		d[u] = depth;
		s[u] = s[f] + v[u];
		fa[u][0] = f;
		for (int i = 1; i <= lg[depth]; i++) {
			fa[u][i] = fa[fa[u][i - 1]][i - 1];
		}

		for (auto v : e[u]) {
			if (v != f) {
				pre(v, u, depth + 1);
			}
		}
	}

	int lca(int u, int v) {
		if (d[u] < d[v]) {
			swap(u, v);
		}

		while (d[u] > d[v]) {
			u = fa[u][lg[d[u] - d[v]]];
		}

		if (u == v) {
			return u;
		}

		for (int i = lg[u]; i >= 0; i--) {
			if (fa[u][i] != fa[v][i]) {
				u = fa[u][i];
				v = fa[v][i];
			}
		}

		return fa[u][0];
	}

	void solve() {
		for (int i = 2; i <= n; i++) {
			lg[i] = lg[i / 2] + 1;
		}
		pre(1, 0, 0);
		#ifdef LOCAL_DEBUG
		for (int i = 1; i <= n; i++) {
			cout << s[i] << " ";
		}
		cout << "\n";
		#endif

		while (q--) {
			int u, v;
			cin >> u >> v;
			int anc = lca(u, v);
			#ifdef LOCAL_DEBUG
			cout << "u: " << u << " v: " << v << " anc: " << anc << "\n";
			#endif
			cout << s[u] + s[v] - s[anc] - s[fa[anc][0]] << "\n";
		}
	}
};

void solve() {
	cin >> n >> q >> k;
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}

	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		e[a].push_back(b);
		e[b].push_back(a);
	}

	if (k == 1) {
		subtask_12_to_13::solve();
	} else if (n <= 2000) {
		subtask_1_to_11::solve();
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int T = 1;
	// cin >> T;
	while (T--) {
		solve();
	}

	return 0;
}

最终，我拿到了 55 + 60 + 0 + 32 = 147 分的成绩，应该能超越天津的一等线（用吉林的估计的，因为天津因为疫情那年没有比赛）。

如果算上挂掉的分和赛后补的 T3，应该有 55 + 75 + 40 + 32 = 202 分，除了重庆和浙江之外的省都能达标省一了。可惜比赛时看题不够耐心，T3 这个 40 分比 T4 的部分分要好写啊。

CSP-S 2023自行模拟