Brackets

序言

可以先参考题目: 最长括号匹配_NOI导刊2009提高(1)

正文

首先, 从最简单的入手, 也就是一条链.

这里要求的是 "括号串中有多少个互不相同的子串是合法括号串", 首先, 可以借鉴一下序言中那道题目的思路.

用 dp_length[i] 表示 "括号串以第 i 位结尾的最长合法序列长度", 那么可以得到:

if (bracket[i] == ')')    //')'
{
    if (bracket[i - 1 - dp_length[i - 1]] == '(')
        dp_length[i] = dp_length[i - 1] + 2 + dp_length[i - 2 - dp_length[i - 1]];
}

Why? 若 A, B 是括号匹配的字符串, 那么对于串 "A(B)"(当前位为 ')'), dp_length[i] = dp_length[B] + dp_length[A] + 2.

接下来, 看看 "有多少个互不相同的子串是合法括号串".

用 dp_sum[i] 表示 "括号串以第 i 位结尾的字串中有多少个互不相同的子串是合法括号串", 那么, 不难得到:

if (bracket[i] == ')')    //')'
{
    if (bracket[i - 1 - dp_length[i - 1]] == '(')
    {
        dp_length[i] = dp_length[i - 1] + 2 + dp_length[i - 2 - dp_length[i - 1]];
        dp_count[i] = dp_count[i] + 1 + dp_count[i - 2 - dp_length[i - 1]];
    }
}
dp_sum[i] = dp_sum[i - 1] + dp_count[i];

dp_count[] 的推导也是同理.

至此, 我们已经解决了链的情况. 于是, 我们发现, 通过 dfs 可以将树转化成链!

然而...Time Limit Exceeded...

But why? 原因在于每找到一条链, 都要从根节点开始求解, 而各条链又有很大一部分是重复的.

比如这棵树:

在我们计算了 {1, 2, 3, 5} 这条链后, 根据 dfs 序, 下一条链为 {1, 2, 3, 6}, 其中, 链 {1, 2, 3} 是重复的. 所以只用从 {6} 开始计算即可.

完整代码

注意, 这里dp_sum[], dp_count[], temp[] 都要用 long long 类型, 否则最后 4 个测试点过不去.

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int VNUM = 5e5 + 5;
const int ENUM = 5e5 + 5;

struct Edge
{
    int end;
    int next;
};

Edge edge[ENUM << 1];
int head[VNUM];
int edgestamp;

int dp_length[VNUM];
long long dp_count[VNUM];
long long dp_sum[VNUM];
int id[VNUM];   //dfs链第 i 位为节点 id[i]
char sequence[VNUM];    //dfs链
char bracket[VNUM]; //原括号串
long long temp[VNUM];   //si 中有多少个互不相同的子串是合法括号串
long long ans;
int lower;  //记录重复位置


void addEdge(int u, int v);
void dfs(int depth, int u, int father); //当前深度, 当前节点, 父节点
void dynamic(int upper);
int main()
{
    int n;

    memset(bracket, '#', sizeof(bracket));

    scanf("%d", &n);
    scanf("%s", bracket + 1);
    for (register int i = 2; i <= n; i++)
    {   
        int u;

        scanf("%d", &u);
        addEdge(u, i);
        addEdge(i, u);
    }
    lower = 0;  //开始时, 没有重复
    dfs(1, 1, 0);
    ans = 0;
    for (register int i = 1;  i <= n; i++)  //异或和
        ans ^= (temp[i] * i);
    printf("%lld\n", ans);

    return 0;
}
void addEdge(int u, int v)
{
    edge[++edgestamp].end = v;
    edge[edgestamp].next = head[u];
    head[u] = edgestamp;
}
void dfs(int depth, int u, int father)
{
    bool isLeaf = true;

    sequence[depth] = bracket[u];
    id[depth] = u;
    for (register int i = head[u]; i != 0; i = edge[i].next)
    {
        int v = edge[i].end;

        if (v == father)
            continue;
        isLeaf = false;
        dfs(depth + 1, v, u);
    }
    if (isLeaf) //是叶节点, 说明找到了一条链
        dynamic(depth);
    lower--;    //回溯, 重复位置上移
}
void dynamic(int upper)
{
    for (register int i = lower + 1; i <= upper; i++)   //重复部分保留
        dp_length[i] = dp_count[i] = dp_sum[i] = 0;
    for (register int i = lower + 1; i <= upper; i++)
    {
        if (sequence[i] == ')') //')'
        {
            if (sequence[i - 1 - dp_length[i - 1]] == '(')
            {
                dp_length[i] = dp_length[i - 1] + 2 + dp_length[i - 2 - dp_length[i - 1]];
                dp_count[i] = dp_count[i] + 1 + dp_count[i - 2 - dp_length[i - 1]];
            }
        }
        dp_sum[i] = dp_sum[i - 1] + dp_count[i];
        temp[id[i]] = dp_sum[i];    //一个点只会被访问一次
    }
    lower = upper;  //修改重复位置
}