P5658 [CSP-S2019] 括号树

对于特殊性质fi=i-1，原图是一条链，注意到当前节点是‘ (’不会产生贡献，‘)’才会产生，那么思考怎么的计算这个贡献。

()()()：每个位置贡献是0,1,0,2,0,3。答案统计出来就是说0,1,1,3,3,6。

())()：贡献是0,1,0,0,1。答案是0,1,1,1,2。

()(()):0,1,0,0,1,2. 0,1,1,1,2,4。

右括号需要匹配左括号，所以将左括号的位置加入一个栈中，匹配成功就弹出，每个右括号的贡献就是他所匹配的左括号的前一个右括号的贡献值+1，这样对于链的情况就解决了。

树上也可以用同样的思路，注意递归会对栈有修改，所以回溯时要复原。

 1 #include <bits/stdc++.h>

 2 #define inf 0x3f3f3f3f

 3 #define ll long long

 4 #define maxn 500005

 5 //#define loveGsy

 6 using namespace std;

 7 int n;

 8 char c[maxn];

 9 int head[maxn], nxt[maxn], to[maxn], cnt, fa[maxn];

10 ll lst[maxn], sum[maxn], ans;

11 int s[maxn], top;

12

13 void add(int u, int v) {

14     nxt[++cnt] = head[u];

15     head[u] = cnt;

16     to[cnt] = v;

17 }

18

19 void dfs(int x) {

20     int tmp = 0;

21     if (c[x] == ')') {

22         if (top) {

23             tmp = s[top];

24             lst[x] = lst[fa[tmp]] + 1;

25             --top;

26         }

27     }

28     else if (c[x] == '(') s[++top] = x;

29     sum[x] = sum[fa[x]] + lst[x];

30     for (int i = head[x]; i; i = nxt[i]) dfs(to[i]);

31     if (tmp != 0) s[++top] = tmp;

32     else if (top) --top;

33     //回溯复原

34 }

35

36 int main() {

37 #ifdef loveGsy

38     freopen("a.in", "r", stdin);

39     freopen("a.out", "w", stdout);

40 #endif

41     scanf("%d", &n);

42     scanf("%s", c + 1);

43     for (int i = 2; i <= n; i++) {

44         int f;

45         scanf("%d", &f);

46         add(f, i);

47         fa[i] = f;

48     }

49     dfs(1);

50     for (int i = 1; i <= n; i++)

51         ans ^= sum[i] * (ll)i;

52     printf("%lld", ans);

53     return 0;

54 }

巴特西

P5658 [CSP-S2019] 括号树

最新文章

热门文章