洛谷 P5658 【括号树】

题库：洛谷
题号：5658
题目：括号树
link ：https://www.luogu.com.cn/problem/P5658

55分链做法 ：这道题链的做法能给很多分，我们设一个右括号的贡献值为当前序列加上这个右括号后可以多获得的匹配数（左括号没有贡献值）。

观察序列1：

()()()

())()

()(())

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 #define int unsigned long long//数据原因 
 4 using namespace std;
 5 int n, q[1000001], sum[1000001], tot[1000001], ans;//tot是贡献值，sum是贡献值总和 
 6 char s[1000001];
 7 stack < int > pru;//栈存左括号的位置 
 8 signed main()
 9 {
10     scanf("%llu", &n);
11     scanf("%s", s + 1);
12     for(register int i = 1; i <= n; ++i)
13     {
14         scanf("%llu", &q[i]);
15     }
16     for(register int i = 1; i <= n; ++i)//遍历链序列(都是连续的) 
17     {
18         if(s[i] == '(')//左括号 
19         {
20             pru.push(i);//push进栈中，用来存第一个左括号的位置 
21         }
22         else//右括号 
23         {
24             if(pru.size() != 0)//判断栈非空 
25             {
26                 int l = pru.top();//取出最近左括号的位置(没用过的) 
27                 tot[i] = tot[l - 1] + 1;//上一个后括号的贡献值 + 1 
28                 pru.pop();//弹出栈 
29             }
30         }
31         sum[i] = sum[i - 1] + tot[i];//sum记录贡献值总和 
32     }
33     ans = sum[1];
34     for(register int i = 2; i <= n; ++i)//异或 
35     {
36         ans ^= i * sum[i];
37     }
38     printf("%llu", ans);
39     return 0;
40 }

满分做法 ：其实很简单，只需要把在链上完成的操作转换到树上来完成就行了，但是要注意回溯，而且之前的最近的左括号的上一个括号的贡献值变为最近的左括号的父亲的贡献值，因为树上一个点的上一个值就是这个点的父亲。

code：

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 #define int unsigned long long//此题数据很大 
 4 using namespace std;
 5 int n, sum[500001], tot[500001], ans, head[500001], num, fa[500001];
 6 char s[500001];
 7 stack < int > pru;
 8 struct node//链式前向星 
 9 {
10     int next, to;
11 }stu[1000001];
12 inline void add(int x, int y)//加边 
13 {
14     stu[++num].next = head[x];
15     stu[num].to = y;
16     head[x] = num;
17     return;
18 }
19 inline void dfs(int u, int father)//树上的链 
20 {
21     int l = -1;//回溯的需要 
22     if(s[u] == '(')
23     {
24         l = 0;//表示回溯需要pop 
25         pru.push(u);
26     }
27     else
28     {
29         if(pru.size() != 0)
30         {
31             l = pru.top();
32             tot[u] = tot[fa[l]] + 1;//最近左括号父节点贡献值 + 1 
33             pru.pop();
34         }
35     }
36     sum[u] = sum[fa[u]] + tot[u];//计算总贡献值 
37     for(register int i = head[u]; i; i = stu[i].next)//搜索 
38     {
39         int k = stu[i].to;
40         if(k != father)//判节点是否可以搜 
41         {
42             dfs(k, u); 
43         }
44     }
45     if(l == 0)//回溯 
46     {
47         pru.pop();
48     }
49     else if(l != -1)//如果 = -1就代表什么都没push或pop 
50     {
51         pru.push(l);
52     }
53     return;
54 }
55 signed main()
56 {
57     scanf("%llu", &n);
58     scanf("%s", s + 1);
59     for(register int i = 2; i <= n; ++i)
60     {
61         scanf("%llu", &fa[i]);
62         add(i, fa[i]);//加边 
63         add(fa[i], i);//加反向边 
64     }
65     dfs(1, -1);//搜索 
66     ans = sum[1];
67     for(register int i = 2; i <= n; ++i)//异或 
68     {
69         ans ^= i * sum[i];
70     }
71     printf("%llu", ans);
72     return 0;
73 }

参见：https://www.luogu.com.cn/blog/266011/solution-p5658

洛谷 P5658 【括号树】

推荐阅读