题解 | DEF

D. 圆

不会这个题。这个做法是有人告诉我的。

经典把序列复制一遍放在后面，那么每一个长度为 的区间都是一种可能的环。

跑一次类似 CF1399F 的做法。每个长度为 的区间算一下。

E. 外向树

生まれた時から知ってたのさ

この街に雪が降ることを

それこそ宇宙が始まるずっと前から

君と僕が出会うように

小清新 DS。

限制转化成点集 的虚树上，叶节点的个数。

一个点 会被计入贡献，当且仅当其子树里面没有任何一个点 也处在点集中，那也就是说：

任意性命题总是不太好处理的，如果只用判断 个位置就好了。

设 的子树中所有点编号的集合中，点 在编号上的前驱后继，分别记作 和 。那么点 满足条件意味着 。

因为 ，所以大于和小于都只用判一侧，从而：

另一侧对称。

通过启发式合并或线段树合并等手段，求出 和 是容易的。

一次询问的答案就是求有多少个 同时满足

也就是有 个四元组 ，每次询问给定一个四元组 ，求这 个四元组中有多少个与询问的四元组满足偏序关系 。这是个四维偏序，可以强行 解决。

区间的限制带来了两个维度，但是转化到这一步之后答案就满足了可差分性，经典差分减一维，把询问差分成 的前缀以及 的前缀，答案就是后者减前者。分治或者树套树解决即可。复杂度 。

似乎有 爆标做法。

/*
 * Copyright© 2024 Ackerlanna & Heratino. All rights reserved.
 * author: Ackerlanna & Heratino
 * Problem: 【牛客练习赛122】 E
 * Tag: 虚树, 启发式合并, 分治, 数据结构
 * Memory Limit: 512MiB
 * Time Limit: 1000ms
 * Source: 牛客练习赛122
 */

// Narcissu / どうか安寧な記憶を

#include <bits/stdc++.h>
using i64 = long long;

//{{{闪耀的一等星
char buf[1 << 20], *P1 = buf, *P2 = buf;
inline char gc() {
	if (P1 == P2)
		P2 = (P1 = buf) + fread(buf, 1, 1 << 20, stdin);
	return P1 == P2 ? EOF : *P1++;
}

inline i64 read() {
	i64 s = 0, w = 1;
	char c = gc();
	while (!isdigit(c)) {
		if (c == '-')
			w = -1;
		c = gc();
	}
	while (isdigit(c))
		s = (s << 3) + (s << 1) + (c ^ 48), c = gc();
	return s * w;
}
//}}}

constexpr int N = 1e5 + 10;
int a[N];
int n, m;

std::basic_string<int> G[N];
inline void add(int u, int v) {G[u] += v;}

int fa[N], dep[N], siz[N], son[N], dfc;
void dfs1(int u) {
	dep[u] = dep[fa[u]] + 1;
	siz[u] = 1;
	for (const int &v : G[u]) {
		if (v == fa[u])
			continue;
		fa[v] = u;
		dfs1(v);
		siz[u] += siz[v];
		if (siz[v] > siz[son[u]])
			son[u] = v;
	}
}
int prev[N], succ[N];

std::set<int> number;
inline void del0(int u) {
	for (const int &v : G[u]) {
		if (v == fa[u])
			continue;
		del0(v);
	}
	number.erase(u);
}
inline void get0(int u) {
	number.insert(u);
	for (const int &v : G[u]) {
		if (v == fa[u])
			continue;
		get0(v);
	}
}

void dfs(int u, bool light) {
	// 先递归轻儿子以防重儿子影响贡献
	for (const int &v : G[u]) {
		if (v == fa[u] || v == son[u])
			continue;
		dfs(v, true);
		del0(v);
	}

	if (son[u])	dfs(son[u], false);

	number.insert(u);
	for (const int &v : G[u]) {
		if (v == fa[u] || v == son[u])
			continue;
		get0(v);
	}
	auto it = number.find(u);
	if (it != number.begin())
		prev[u] = *std::prev(it);
	else
		prev[u] = -1;

	if (std::next(it) != number.end())
		succ[u] = *std::next(it);
	else
		succ[u] = n + 1;

	if (light)
		del0(u);
}

struct queries {
	int p;
	int L, R;
	int num, C;
	bool operator < (const queries &t) {
		return p < t.p;
	}
};

int ans[N];
std::vector<queries> q;
int tr[N];
inline int lowbit(int x) {return x & -x;}
inline void addT(int pos, int k) {
	for (int i = pos; i < N; i += lowbit(i))
		tr[i] += k;
}
inline int query(int pos) {
	int res = 0;
	for (int i = pos; i > 0; i -= lowbit(i))
		res += tr[i];
	return res;
}

int p[N];
void Divide(int l, int r, std::vector<queries> &qry) {
	if (l == r) {
		std::sort(qry.begin(), qry.end(), [&] (auto x, auto y) {
				return x.L < y.L;
				});
		for (const auto &[pos, L, R, num, C] : qry) {
			if (prev[p[l]] < L && succ[p[l]] > R)
				ans[num] += C;
		}
		return ;
	}
	int mid = l + r >> 1;
	std::vector<queries> lft, rgt;
	for (const auto &x : qry) {
		if (x.p <= mid)
			lft.push_back(x);
		else
			rgt.push_back(x);
	}

	// 左右按 l 排序
	Divide(l, mid, lft);
	Divide(mid + 1, r, rgt);

	int lpos = l;
	for (const auto &[pos, L, R, num, C] : rgt) {
		while (lpos <= mid && prev[p[lpos]] < L)
			addT(succ[p[lpos++]], 1);
		ans[num] += ((lpos - l) - query(R)) * C;
	}
	for (int i = l; i < lpos; i++)
		addT(succ[p[i]], -1);

	// 归并
	std::inplace_merge(p + l, p + mid + 1, p + r + 1, [&](int x, int y) {
			return prev[x] < prev[y];
			});
	std::merge(lft.begin(), lft.end(), rgt.begin(), rgt.end(), qry.begin(), [&](auto x, auto y) {
			return x.L < y.L;
			});
}

/* 无法忘却的记忆与苍蓝之梦 */
int main() {
#ifdef AckerlannaHeratino
	freopen("input.txt", "r", stdin);
#endif
	n = read(), m = read();
	for (int i = 1; i < n; i++) {
		int u = read(), v = read();
		add(u, v), add(v, u);
	}
	dfs1(1);
	dfs(1, true);

	//	for (int i = 1; i <= n; i++)
	//		std::cerr << prev[i] << " \n"[i == n];
	//	for (int i = 1; i <= n; i++)
	//		std::cerr << succ[i] << " \n"[i == n];

	for (int i = 1; i <= n; i++)	p[i] = i;
	for (int i = 1; i <= m; i++) {
		int l = read(), r = read();
		if (l == r) {
			ans[i] = 0;
		} else {
			if (l != 1)
				q.push_back({l - 1, l, r, i, -1});
			q.push_back({r, l, r, i, 1});
		}
	}
	std::sort(q.begin(), q.end());
	Divide(1, n, q);
	for (int i = 1; i <= m; i++)
		std::cout << ans[i] << '\n';
	return 0;
}

F. 括号匹配

鈴虫の音さえ消えて

祭囃子も聞こえない

难点大概是想不到用网络流做吧。

限制很多，这种相互约束的东西要么拆或者简化约束，要么考虑用网络流来整体解决。 怎么用网络流在一个括号序列中找到一个合法括号串？从 向所有左括号连一条流量为 的边，所有右括号向 连一条边，那么最大流中，找到那些有流量的边就可以得到最长的一个括号子序列了。

从而，这个题三个只能留一个的限制只要新建一个虚点 分别连向这三个点。 到 容量为 ，而 分别向这三个点连一条容量为 的边。

现在再加上权值的限制，容易在边权上加入费用的限制，跑最大费用最大流即可。

/*
 * Copyright© 2024 Ackerlanna & Heratino. All rights reserved.
 * author: Ackerlanna & Heratino
 * Problem: 【牛客练习赛122】 F
 * Tag: 网络流
 * Memory Limit: 512MiB
 * Time Limit: 1000ms
 * Source: 牛客练习赛122
 */

// Narcissu / どうか安寧な記憶を

#include <bits/stdc++.h>
using i64 = long long;

constexpr int N = 2200 * 4;
constexpr int M = 4 * N;
constexpr int inf = 0x3f3f3f3f;

struct edge {
	int flow, cap;
	int cost;
	int u, v;
} E[M];

std::basic_string<int> G[N];
int now[N];

int idx = 0;
inline void add(int u, int v, int cap, int cost) {
	E[idx] = {0, cap, cost, u, v};
	G[u] += idx++;
	E[idx] = {0, 0, -cost, v, u};
	G[v] += idx++;
}

int s, t;
int dis[N], dep[N];
bool inq[N];

bool SPFA() {
	memset(dis, 0x3f, sizeof(dis));
	memset(inq, 0, sizeof(inq));
	std::queue<int> q;
	q.push(s), inq[s] = 1;
	dis[s] = 0;

	while (!q.empty()) {
		int u = q.front();
		q.pop();
		inq[u] = false;

		for (const int &i : G[u]) {
			const auto &e = E[i];
			if (e.cap == e.flow)
				continue;
			if (dis[e.v] > dis[e.u] + e.cost) {
				dis[e.v] = dis[e.u] + e.cost;
				if (!inq[e.v])
					q.push(e.v), inq[e.v] = true;
			}
		}
	}
	return dis[t] < inf;
}

bool bfs() {
	memset(dep, 0x3f, sizeof(dep));
	std::queue<int> q;
	q.push(s);
	dep[s] = 0;

	while (!q.empty()) {
		int u = q.front();
		now[u] = 0;
		q.pop();

		for (const int &i : G[u]) {
			const auto &e = E[i];
			if (e.cap == e.flow)
				continue;
			if (dis[e.v] == dis[e.u] + e.cost && dep[e.v] == inf) {
				dep[e.v] = dep[e.u] + 1;
				q.push(e.v);
				if (e.v == t)
					return true;
			}
		}
	}
	return false;
}

int FLOW;
i64 COST;
int global;
int dfs(int u, i64 res) {
	if (u == t || !res)
		return res;

	int flow = 0;
	for (int &i = now[u]; i < G[u].size() && res; i++) {
		auto &edg = E[G[u][i]];
		auto &rev = E[G[u][i] ^ 1];
		if (edg.cap > edg.flow && dep[edg.v] == dep[edg.u] + 1 && dis[edg.v] == dis[edg.u] + edg.cost) {
			int k = dfs(edg.v, std::min(0ll + edg.cap - edg.flow, res));
			if (!k) {
				dep[edg.v] = inf;
				continue;
			}
			edg.flow += k;
			rev.flow -= k;
			flow += k;
			res -= k;
			global += edg.cost;
		}
	}
	return flow;
}

int n, m;
std::string str;
int weight[N];

std::vector<int> in;
std::vector<int> out;
int tot;
bool vis[N];

// 確かな愛が視たいなら、音に成って今逃げ出して！
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	std::cin >> n >> m;
	std::cin >> str;
	str = ' ' + str;
	for (int i = 1; i <= n; i++)
		std::cin >> weight[i];

	tot = 2 * n;
	s = 2 * n + m + 1;
	t = 2 * n + m + 2;
	for (int i = 1; i <= n; i++) {
		add(i, i + n, 1, -weight[i]);
	}
	for (int i = 1; i <= m; i++) {
		tot++;
		int x, y, z;
		std::cin >> x >> y >> z;
		if (str[x] == '(') {
			add(s, tot, 1, 0);
			add(tot, x, 1, 0);
			add(tot, y, 1, 0);
			add(tot, z, 1, 0);
			vis[x] = vis[y] = vis[z] = true;
		} else {
			add(x + n, tot, 1, 0);
			add(y + n, tot, 1, 0);
			add(z + n, tot, 1, 0);
			add(tot, t, 1, 0);
			vis[x] = vis[y] = vis[z] = true;
		}
	}
	tot = 2 * n + m + 2;

	int lst = -1;
	for (int i = n; i >= 1; i--) {
		if (str[i] == ')') {
			tot++;
			add(tot, i, 1, 0);
			if (lst != -1)
				add(tot, lst, inf, 0);
			lst = tot;
		} else {
			if (lst != -1)
				add(i + n, lst, 1, 0);
		}
	}
	for (int i = 1; i <= n; i++)
		if (!vis[i]) {
			if (str[i] == '(') {
				add(s, i, 1, 0);
			} else {
				add(i + n, t, 1, 0);
			}
		}

	i64 sum = 0;
	for (int i = 1; i <= n; i++)
		sum += weight[i];
	while (SPFA()) {
		global = 0;
		bfs();
		FLOW += dfs(s, inf);
		COST += global;
	}
	bool flag = true;
	for (auto i : G[s]) {
		if (E[i].flow != E[i].cap) {
			flag = false;
		}
	}
	for (auto i : G[t]) {
		if (E[i ^ 1].flow != E[i ^ 1].cap) {
			flag = false;
		}
	}
	if (flag) {
		std::cout << "Yes\n";
		std::cout << sum + COST << '\n';
	} else {
		std::cout << "No\n";
	}
	return 0;
}