Description
给你一个有 $n$ 个点的树，每个点上有一个符号，为左括号或右括号，定义一个字符串合法当且仅当这个字符串中的每一个左括号都有一个唯一的与之对应的右括号，定义 $k_i$ 为从根节点 1 到点 $i$ 的字符串中互不相同的合法括号串的个数。
现在请你求出 $(1 \times k_1) \; \text{xor} \; (1 \times k_1) \; \text{xor} \; … \; (n \times k_n)$ 的值。
Solution
设 $dp[x]$ 表示一端为点 $x$ 的合法括号串的个数，则 $k_x = k_{f_x} + dp[x]$，其中 $f_x$ 为点 $x$ 的父亲的编号。
再用 $pre_x$ 表示最后一个未匹配的 ( 的位置来辅助 DP 即可。
具体转移可以参见 Code 部分。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include <cstdio>
#define maxN 500010
char st[maxN];
struct node{ long long x, y, g; } b[maxN];
long long ans[maxN], pre[maxN], dp[maxN], f[maxN], h[maxN];
long long len = 0;
void ins (long long x, long long y)
{
len++;
b[len].x = x;
b[len].y = y;
b[len].g = h[x];
h[x] = len;
}
void dfs (long long x)
{
if(st[x] == '(')
{
pre[x] = x;
}
else if(f[x] && pre[f[x]])
{
dp[x] = dp[f[pre[f[x]]]] + 1;
pre[x] = pre[f[pre[f[x]]]];
}
ans[x] = ans[f[x]] + dp[x];
for(long long i = h[x];i > 0;i = b[i].g)
{
long long y = b[i].y;
dfs(y);
}
}
int main ()
{
long long n = 0;
scanf("%lld", &n);
scanf("%s", st + 1);
for(long long i = 2;i <= n; i++)
{
scanf("%lld", &f[i]);
ins(f[i], i);
}
dfs(1);
long long Ans = 1 * ans[1];
for(long long i = 2;i <= n; i++)
{
Ans ^= i * ans[i];
}
printf("%lld", Ans);
return 0;
}
|