20220316 - 模拟赛 | Final Fantasy = xixike = 人间忽晚，山河已秋

树的重心 + 二分，后缀自动机 + LCT + 树状数组，搜索

# A. 跳蚤王国的宰相

一上来就冲了个换根 $\text{dp}$ ，然后过了小样例和自己手造的样例，感觉还挺稳的，考到一半发现题看假了，样例也算假了，想成要删多少个点了（我就说这题怎么这么水 QwQ）。

回到本题，首先重心的答案肯定是 0。

考虑重心的性质：如果一个点为重心，那么它的所有子树的大小都不大于 $\frac n2$ ，

所以我们只要把一个点为根的情况下它所有子树的大小全部减到 $\frac n2$ 以下即可。

详细过程：

先把重心拎出来，把它的所有子树从大到小排序，并做个前缀和存到 $sum_i$ 里。然后依次递归处理每一棵子树。
对于每棵子树进行分类讨论，设 $id$ 为子树的根， $x$ 为每棵字数内的点：
- 如果 $id$ 本身就是重心（重心可能有多个），直接更新答案 $ans_x = (x\ != id)$ ，如果当前的 $x$ 不是 $id$ 只需要切一条边即可。
- 如果减去 $sum_{pos[x] - 1}$ 之后 $x$ 可以成为重心，那么在 $1 \sim pos[x] - 1$ 之间二分需要切掉多少条边（也就是切多少棵子树，然后把这些子树接到 $x$ 下面）。
- 如果减去之后 $x$ 依然不能成为重心，那么就去 $pos[x] + 1 \sim tot$ 里面二分找答案。
各种边界什么的就不细讲了，比较繁琐，直接看代码吧。

	#include <bits/stdc++.h>
	#define ll long long
	#define pb push_back

	using namespace std;

	namespace IO{
	inline ll read(){
	ll x = 0;
	char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 1e6 + 10;
	int n, rt;
	vector <int> g[N];
	int siz[N], mx[N];
	int ans[N];

	inline void getroot(int x, int fa){
	siz[x] = 1, mx[x] = 0;
	for(auto y : g[x]){
	if(y == fa) continue;
	getroot(y, x);
	siz[x] += siz[y], mx[x] = max(mx[x], siz[y]);
	}
	mx[x] = max(mx[x], n - siz[x]);
	if(mx[x] < mx[rt] \|\| !rt) rt = x;
	}

	int s[N], tot, id;
	int pos[N], sum[N];

	inline bool cmp(int x, int y) {return siz[x] > siz[y];}

	inline void dfs(int x, int fa, int id){
	int w = n - siz[x];
	if(n - siz[id] <= n / 2) ans[x] = (x != id);
	else if(w - (sum[pos[id] - 1]) <= n / 2){
	int l = 0, r = pos[id] - 1;
	while(l < r){
	int mid = (l + r) >> 1;
	if(w - sum[mid] <= n / 2 \|\| n - siz[id] - sum[mid - 1] <= n / 2) r = mid;
	else l = mid + 1;
	}
	ans[x] = l;
	}else{
	int l = pos[id] + 1, r = tot;
	while(l < r){
	int mid = (l + r) >> 1;
	if(w - sum[mid] + siz[id] <= n / 2 \|\| n - sum[mid - 1] <= n / 2) r = mid;
	else l = mid + 1;
	}
	ans[x] = l - 1;
	}
	for(auto y : g[x]) if(y != fa) dfs(y, x, id);
	}

	inline void solve(){
	for(auto y : g[rt]) s[++tot] = y;
	sort(s + 1, s + 1 + tot, cmp);
	for(int i = 1; i <= tot ; ++i) sum[i] = sum[i - 1] + siz[s[i]], pos[s[i]] = i;
	for(auto y : g[rt]) dfs(y, rt, y);
	}

	signed main(){
	n = read();
	for(int i = 1; i < n; ++i){
	int u = read(), v = read();
	g[u].pb(v), g[v].pb(u);
	}
	getroot(1, 0), getroot(rt, 0);
	solve();
	for(int i = 1; i <= n; ++i) write(ans[i]), puts("");
	return 0;
	}
	// X.K.

# B. 事情的相似度

考场上完全没思路，暴力也懒得打了（其实是没时间）。

首先转换一下题意：建出后缀自动机，题目就是求 $l \sim r$ 内两个串的最长公共后缀，就是所代表节点的 $lca$ 的 $len$ 。

把询问离线下来，对于每个 $r$ 依次处理。

每加进去一个字符，我们把 $\text{SAM}$ 中相应的点到根的路径覆盖上颜色 $i$ （ $i$ 为字符编号），这个过程使用 $\text{LCT}$ 维护。

然后用树状数组统计从根到每个点的最大值（这里由于是从根到每个点，所以在树状数组上是一段后缀，插入和查询的循环要反过来）。查询的时候直接查询就可以了。

	#include <bits/stdc++.h>
	#define ll long long
	#define pb push_back
	#define fi first
	#define se second

	using namespace std;

	namespace IO{
	inline ll read(){
	ll x = 0;
	char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 2e5 + 10;
	typedef pair<int, int> P;
	int n, m, lst = 1, tot = 1;
	char s[N];
	vector <P> q[N];
	int pos[N], len[N], fa[N];

	namespace SAM{
	int siz[N], ch[N][27];
	inline int insert(int c){
	int p = lst, np = ++tot;
	lst = np;
	len[np] = len[p] + 1, siz[np]++;
	while(p && !ch[p][c]) ch[p][c] = np, p = fa[p];
	if(!p) fa[np] = 1;
	else{
	int q = ch[p][c];
	if(len[q] == len[p] + 1) fa[np] = q;
	else{
	int nq = ++tot;
	len[nq] = len[p] + 1, fa[nq] = fa[q], siz[nq] = 0;
	for(int i = 0; i < 26; ++i) ch[nq][i] = ch[q][i];
	while(p && ch[p][c] == q) ch[p][c] = nq, p = fa[p];
	fa[q] = fa[np] = nq;
	}
	}
	return np;
	}
	}
	using SAM :: insert;

	namespace BIT{
	int c[N], mx[N];

	inline void add(int x, int v){
	for(; x; x -= x & (-x)) c[x] = max(c[x], v);
	}

	inline int query(int x){
	int res = 0;
	for(; x < N; x += x & (-x)) res = max(res, c[x]);
	return res;
	}
	}
	using BIT :: add;
	using BIT :: query;

	namespace LCT{
	#define ls ch[x][0]
	#define rs ch[x][1]

	int ch[N][2], col[N], tag[N];

	inline bool nroot(int x) {return ch[fa[x]][0] == x \|\| ch[fa[x]][1] == x;}

	inline void pushdown(int x){
	if(tag[x]){
	if(ls) col[ls] = tag[ls] = tag[x];
	if(rs) col[rs] = tag[rs] = tag[x];
	tag[x] = 0;
	}
	}

	inline void push(int x){
	if(nroot(x)) push(fa[x]);
	pushdown(x);
	}

	inline void rotate(int x){
	int y = fa[x], z = fa[y], k = ch[y][1] == x, w = ch[x][k ^ 1];
	if(nroot(y)) ch[z][ch[z][1] == y] = x;
	ch[x][k ^ 1] = y, ch[y][k] = w;
	if(w) fa[w] = y;
	fa[y] = x, fa[x] = z;
	}

	inline void splay(int x){
	push(x);
	int y = x, z;
	while(nroot(x)){
	y = fa[x], z = fa[y];
	if(nroot(y)) rotate((ch[z][1] == y) ^ (ch[y][1] == x) ? x : y);
	rotate(x);
	}
	}

	inline void access(int x, int c){
	int y;
	for(y = 0; x; x = fa[y = x]) splay(x), add(col[x], len[x]), rs = y;
	col[y] = tag[y] = c;
	}
	}
	using LCT :: access;

	int ans[N];

	signed main(){
	n = read(), m = read();
	scanf("%s", s + 1);
	for(int i = 1; i <= n; ++i) pos[i] = insert(s[i] - '0');
	for(int i = 1; i <= m; ++i){
	int l = read(), r = read();
	q[r].pb(P(l, i));
	}
	for(int i = 1; i <= n; ++i){
	access(pos[i], i);
	for(auto x : q[i]) ans[x.se] = query(x.fi);
	}
	for(int i = 1; i <= m; ++i) write(ans[i]), puts("");
	return 0;
	}
	// X.K.

# C. 蛐蛐国的修墙方案

一开始写了个 $O(n)$ 的做法（贪心左边能填括号时就填左括号），然后过小样例了，手造了几组样例也都过了，感觉自己非常 $nb$ 。

然后生成了 (()())() 的所有合法序列，放到代码里跑了跑，结果一大堆最后一位是 ( 的，于是知道自己想假了。又想了想，感觉报搜找环就行，然后找到环之后让环中编号最小的点为 ( ，剩下的依次推过去，测了一车小样例都过了，感觉自己非常稳。

离比赛结束的时候教练给大样例了，测了一发，然后 $\text{WA}$ 了？？？

立马意识到还得 $2^{cnt}$ 枚举哪些边为 ( ，哪些边为 ) ， $cnt$ 是环的个数。

一顿乱改总算是过了。

由于一个环只有两种填左右括号的情况，所以复杂度就是 $O(2^{cnt})$ 的，2 元环可以直接令小的为 ( ，所以我们只需要考虑 4 元环及以上，所以复杂度最大是 $O(2^{\frac n4})$ 的。

本题保证有解（虽然没写），无解的情况是出现奇环。

	#include <bits/stdc++.h>
	#define ll long long
	#define pb push_back

	using namespace std;

	namespace IO{
	inline ll read(){
	ll x = 0;
	char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 110;
	int n, cnt, top, flag, tot;
	int p[N], stk[N], a[N];
	char s[N];
	bool vis[N];
	vector <int> g[N];

	inline void dfs(int x){
	if(vis[x]) return void();
	stk[++top] = x, vis[x] = 1, dfs(p[x]);
	}

	inline void prework(int x){
	top = 0, dfs(x);
	if(top == 2) a[min(stk[1], stk[2])] = 1;
	else{
	tot++;
	for(int i = 1; i <= top; ++i) g[tot].pb(stk[i]);
	}
	}

	inline bool check(){
	int cnt = 0;
	for(int i = 1; i <= n; ++i){
	cnt += (a[i] ? 1 : -1);
	if(cnt < 0) return 0;
	}
	for(int i = 1; i <= n; ++i) putchar(a[i] ? '(' : ')');
	puts("");
	return 1;
	}

	inline void solve(int x){
	if(flag) return;
	if(x == tot + 1){
	if(check()) flag = 1;
	return;
	}
	for(int i = 0; i < (int)g[x].size(); ++i) a[g[x][i]] = i & 1;
	solve(x + 1);
	for(int i = 0; i < (int)g[x].size(); ++i) a[g[x][i]] ^= 1;
	solve(x + 1);
	}

	signed main(){
	// freopen("C.in", "r", stdin);
	// freopen("C.out", "w", stdout);
	n = read();
	for(int i = 1; i <= n; ++i) p[i] = read();
	for(int i = 1; i <= n; ++i) if(!vis[i]) prework(i);
	solve(1);
	return 0;
	}
	// X.K.

# A. 跳蚤王国的宰相

# B. 事情的相似度

# C. 蛐蛐国的修墙方案

AT1983 [AGC001E] BBQ Hard 题解

USACO22OPEN Silver