思路是 KnownError 的思路，但是没有用并查集，而是用栈，且直接用根 DFS，没有从根的儿子开始，WA on #19,#29.

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using ULL = unsigned long long;

#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;

//template above

const int N = 5e5 + 10;

int n; vector<int> e[N], re[N];
int top; int c[N];
int lst[N], bk[N];
int dfn[N], dn;
int mi[20][N];
bool st[N]; vector<int> id;
int d[N];

void dfs(int u, int fa) {
	bk[u] = -1;
	if (c[u] == 1) bk[u] = lst[top], lst[top] = fa, top ++ ;
	else if (top) {
		top -- ; bk[u] = top + 1; assert(~lst[top]);
		re[lst[top]].push_back(u);
	}
	for (int v : e[u]) {
		if (v == fa) continue ;
		d[v] = d[u] + 1; dfs(v, u);
	}
	if (~bk[u]) {
		if (c[u] == 1) assert(top), lst[ -- top] = bk[u];
		else top = bk[u];
	}
}
void dfs1(int u, int fa) {
	id.push_back(u); st[u] = 1;
	for (int v : re[u]) if (v != fa) dfs1(v, u);
}
void dfs2(int u, int fa) {
	mi[0][dfn[u] = ++ dn] = fa; 
	for (int v : e[u]) if (v != fa) dfs2(v, u);
}
int get(int x, int y) { return dfn[x] < dfn[y] ? x : y; }
int lca(int u, int v) {
	if (u == v) return u;
	if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
	int k = log(v - (u ++ )) / log(2);
	return get(mi[k][u], mi[k][v - (1 << k) + 1]);
}
int dist(int x, int y) { return d[x] + d[y] - 2 * d[lca(x, y)]; }

void solve() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++ ) {
		char ch; scanf(" %c", &ch);
		c[i] = (ch == '(' ? 1 : -1);
	}
	for (int i = 0, u, v; i < n - 1; i ++ ) {
		scanf("%d%d", &u, &v);
		e[u].push_back(v), e[v].push_back(u);
	}
	d[1] = 1; dfs(1, 0); dfs2(1, 0);
//	for (int i = 0; i <= n; i ++ , puts("")) for (int j : re[i]) printf("%d ", j);
	int t = log(n + 1) / log(2) + 1;
	for (int i = 1; i < t; i ++ ) for (int j = 0; j + (1 << i) - 1 <= n; j ++ ) mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << (i - 1))]);
	int res = 0;
	for (int i = 0; i <= n; i ++ ) if (!st[i]) {
		id.clear(); dfs1(i, -1);
		sort(id.begin(), id.end(), [](int x, int y){ return dfn[x] < dfn[y]; });
		int cnt = 0;
		for (int _ = 0; _ < (int)id.size() - 1; _ ++ ) cnt += dist(id[_], id[_ + 1]);
		cnt += dist(id[0], *( -- id.end())); 
		cnt = cnt / 2; res = max(res, cnt);
	} if (res == 1) res = 0; printf("%d\n", res);
}

bool Med;
int main() {
	fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
//	#define xuyiyang
	#ifdef xuyiyang
		freopen("P9655_19.in", "r", stdin); freopen(".out", "w", stdout);
	#endif

	int T = 1;
	while (T -- ) solve();

	fprintf(stderr, "%.3lf ms\n", 1e3 * clock() / CLOCKS_PER_SEC);
	return 0;
}