自动搬运

查看原文

来自洛谷，原作者为

	lrqlrq250 AFOed, さよなら

搬运于2025-08-24 22:37:10，当前版本为作者最后更新于2022-08-24 11:03:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解题思路

其实想清楚如何构造之后就很简单了。

我们考虑连续的单个括号（比如()()）和嵌套的括号（比如(())）这样的两种括号序列，假设他们在一条链上，连续的有 $3$ 个合法括号序列，但是嵌套的只有 $2$ 个，所以我们要把这棵树上所有路径都尽量设计成连续的单个括号这种形式。

一号点的括号已经给出来了。想要构造连续的括号，显然可以对于每一个节点，让它成为和它父节点相反的括号。

这个过程用搜索实现就好了。

看到题解区好像都是用 dfs 写的，因此我选择用 bfs

AC Code

#include <bits/stdc++.h>
using namespace std;
struct Edge{int to, next;}e[200001];
int n, head[100001], tot, ans[100001];
bool vis[100001];

inline void addedge(int u, int v){
	e[++tot].to = v;
	e[tot].next = head[u];
	head[u] = tot;
}

int main(){
	scanf("%d", &n);
	int u, v, tmp;
	for (int i=1; i<n; i++){
		scanf("%d%d", &u, &v);
		addedge(u, v); addedge(v, u);
	}
	queue<int> q; q.push(1);
	vis[1] = 1; ans[1] = 0; 
	while (!q.empty()){
		u = q.front(); q.pop();
		for (int i=head[u]; i; i=e[i].next) if (!vis[e[i].to]){
			v = e[i].to;
			ans[v] = ans[u] ^ 1;
			q.push(v); vis[v] = 1;
		}
	}
	for (int i=1; i<=n; i++) printf("%c", ans[i] ? ')' : '(');
	return 0;
}

貌似跑的还挺快