对于路径全查问题容易想到点分治，考虑怎么统计答案。

不难想到把每条链$Path_{u,v}$拆成$Path_{u,root}$（下称左链）以及$Path_{root,v}$（下称右链），不妨将$root$分给左链。

考虑一条路径如何才是合法的:

• 条件一：路径左括号和右括号的个数相同
• 条件二：左链的任何前缀左括号都不少于右括号
• 条件三：右链的任何后缀右括号的不少于左括号

下面将左括号视作$1$，右括号视作$-1$，来看如何统计条件二的信息。

显然统计前缀和最小值即可知道路径是否合法。

当在括号序列左侧新加入一个左括号时，前缀和最小值加$1$即为新的前缀和最小值。

当在括号序列左侧新加入一个右括号时，前缀和首项添加一个$-1$，其余项全部减$1$右移一位。

当之前的前缀和最小值为负数时，则原前缀和最小值$-1$即为新的前缀和最小值，否则$-1$为新的前缀和最小值。

容易发现条件三和条件二近乎等价，只需交换左右括号权值用相同方法即可。

下面考虑一个合法括号序列的最深嵌套深度是什么。

考虑朴素做法，遇左括号入栈，遇右括号和栈顶左括号一同出栈，这个过程中栈的元素个数的最大值即为最大嵌套深度。

还是将左括号视作$1$，右括号视作$-1$，序列前缀和的最大值即为最大嵌套深度。

但是我们的路径信息是由左链和右链拼接而成的，那么左链的最大前缀和和右链的最大后缀和取max即为这条合法路径的最大嵌套深度。最大前（后）缀和的统计方法和最小前（后）缀和基本相同，这里便不加赘述。

有一个容易被忽视的点是合法括号序列路径是有向的，于是将子树遍历顺序存储下来，倒序再做一遍即可统计全部答案。

下面总结一下做法，点分治搜索时记录以当前点为起点的前缀和最大值，以当前点为起点的前缀和最小值以及路径权值和，当最小前缀和非负时当前半条路径合法，注意以分治重心为端点的路径需要在此时统计，将前缀和最大值和路径权值和存储起来，用桶以权值和为下标存储前缀和最大值，统计完信息后先遍历右链去桶中查找元素，再将左链信息加入桶中，做完所有子树后清空桶，倒置子树遍历顺序再进行一遍相同操作。

代码 $O(nlogn)$

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int N = 40010, M = 80010;
const int offset = 40004;

int n;
int e[M], ne[M], h[N], idx;
char s[N];
bool vis[N];
struct Info {
    int v, d;
}l[N], r[N];
int lt, rt;
int b[M]; 
int res;
int init;

void insert(int u, int v) {
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

int get_sz(int u, int fa) {
    if (vis[u]) return 0;
    int res = 1;
    for (int i = h[u]; ~i; i = ne[i])
        if (e[i] != fa)
            res += get_sz(e[i], u);
    return res;
}

int get_rt(int u, int fa, int tot, int& rt) {
    if (vis[u]) return 0;
    int sum = 1, ms = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        int t = get_rt(j, u, tot, rt);
        ms = max(ms, t);
        sum += t;
    }
    ms = max(ms, tot - sum);
    if (ms <= tot / 2) rt = u;
    return sum;
}

void get_info(int u, int fa, int sl, int tl, int sr, int tr, int sum) {
    if (vis[u]) return;
    sl = (s[u] == ')') ? (min(0, sl) - 1) : (sl + 1);
    tl = (s[u] == '(') ? (max(0, tl) + 1) : (tl - 1);
    sr = (s[u] == '(') ? (min(0, sr) - 1) : (sr + 1);
    tr = (s[u] == ')') ? (max(0, tr) + 1) : (tr - 1);   
    sum = (s[u] == ')') ? sum - 1 : sum + 1;
    if (sl >= 0) {
        l[++lt] = {sum + init, tl};
        if (sum + init == 0) res = max(res, tl);
    }
    if (sr >= 0) r[++rt] = {sum, tr};
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        get_info(j, u, sl, tl, sr, tr, sum);
    }
}

void solve(int u) {
    if (vis[u]) return;
    get_rt(u, -1, get_sz(u, -1), u);
    vis[u] = true;  
    init = (s[u] == ')') ? -1 : 1; 
    vector<int> modify, sons;
    if (init > 0) b[1 + offset] = 1, modify.push_back(1 + offset);
    for (int i = h[u]; ~i; i = ne[i]) {
        lt = rt = 0;
        int j = e[i];
        sons.push_back(j);
        get_info(j, u, init, init, 0, 0, 0);
        for (int k = 1; k <= rt; k++) 
            if (b[offset - r[k].v])
                res = max(res, max(b[offset - r[k].v], r[k].d));  
        for (int k = 1; k <= lt; k++) {
            int t = l[k].v + offset;
            if (b[t] < l[k].d) {
                modify.push_back(t);
                b[t] = l[k].d;
            }
        }
    }
    for (auto item : modify) b[item] = 0;
    if (init > 0) b[1 + offset] = 1, modify.push_back(1 + offset);
    for (int i = sons.size() - 1; ~i; i--) {
        lt = rt = 0;
        int j = sons[i];
        get_info(j, u, init, init, 0, 0, 0);
        for (int k = 1; k <= rt; k++) 
            if (b[offset - r[k].v])
                res = max(res, max(b[offset - r[k].v], r[k].d));  
        for (int k = 1; k <= lt; k++) {
            int t = l[k].v + offset;
            if (b[t] < l[k].d) {
                modify.push_back(t);
                b[t] = l[k].d;
            }
        }
    }
    for (auto item : modify) b[item] = 0;
    for (int i = h[u]; ~i; i = ne[i]) solve(e[i]);
}

int main() {
    cin.tie(0)->ios::sync_with_stdio(false);
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 2; i <= n; i++) {
        int fa;
        cin >> fa;
        insert(i, fa);
        insert(fa, i); 
    }
    for (int i = 1; i <= n; i++) cin >> s[i];
    solve(1);
    cout << res;
    return 0;
}