括号树
【题目背景】
本题中合法括号串的定义如下：
1.0是合法括号串。
2.如果A是合法括号串，则(A)是合法括号串。
3.如果A, B是合法括号串，则AB是合法括号串。
本题中子串与不同的子串的定义如下：
1.字符串S的子串是S中连续的任意个字符组成的字符串。S的子串可用起始位置l与终止位置r来表示，记为S(l,r)(1≤l≤r≤|S|,|S|表示S的长度)。
2.S的两个子串视作不同当且仅当它们在S中的位置不同，即l不同或r不同。
【题目描述】
一个大小为n的树包含n个结点和n-1条边，每条边连接两个结点，且任意两个 结点间有且仅有一条简单路径互相可达。
小Q是一个充满好奇心的小朋友，有一天他在上学的路上碰见了一个大小为n的 树，树上结点从1~n编号，1号结点为树的根。除1号结点外，每个结点有一个父亲 结点，u (2≤ u≤n)号结点的父亲为fu (1 ≤ fu < u)号结点。
小Q发现这个树的每个结点上恰有一个括号，可能是'('或')'。小Q定义si为：将 根结点到i号结点的简单路径上的括号，按结点经过顺序依次排列组成的字符串。
显然si是个括号串，但不一定是合法括号串，因此现在小Q想对所有的i(1≤i≤n) 求岀，si中有多少个互不相同的子串是合法括号串。
这个问题难倒了小Q,他只好向你求助。设si共有ki个不同子串是合法括号串, 你只需要告诉小Q所有ixki的异或和，即：
(1 x k1) xor (2 x k2) xor (3 x k3)xor .…xor (n x kn)其中xor是位异或运算。
【输入格式】
从文件brackets.in中读入数据。
第一行一个整数n，表示树的大小。
第二行一个长为n的由'('与')'组成的括号串，第i个括号表示i号结点上的括号。
第三行包含n-1个整数，第i(1≤i<n)个整数表示i+1号结点的父亲编号fi+1。
【输出格式】
输出到文件brackets.out中。
仅一行一个整数表示答案。
【样例1输入】
5
（（）（）
1 1 2 2
【样例1输出】
6
【样例1解释】
树的形态如下图:
将根到1号结点的简单路径上的括号，按经过顺序排列所组成的字符串为（，子串 是合法括号串的个数为0。
将根到2号结点的简单路径上的括号，按经过顺序排列所组成的字符串为（（，子 串是合法括号串的个数为0。
将根到3号结点的简单路径上的括号，按经过顺序排列所组成的字符串为（），子 串是合法括号串的个数为1。
将根到4号结点的简单路径上的括号，按经过顺序排列所组成的字符串为（（（，子 串是合法括号串的个数为0。
将根到5号结点的简单路径上的括号，按经过顺序排列所组成的字符串为（（），子 串是合法括号串的个数为1。
【数据范围】
相似题推荐
如下图所示，A到B是连通的。假设删除一条细的边的代价是1，删除一条粗的边的代价是2，要让A、B不连通，最小代价是_____(2分)，最小代价的不同方案数是_______(3分)。(只要有一条删除的边不同，就是不同的方案)
如右图所示，共有13个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变(由1变0，或由0变1)。现在要使得所有的格子中的数字都变为0,至少需要 次操作。
（最长路径）给定一个有向无环图，每条边长度为1，求图中的最长路径长度。（第五空2分，其余3分）
输入：第一行是结点数n（不超过100）和边数m，接下来m行，每行两个整数a，b，表示从结点a到结点b有一条有向边。结点标号从0到(n-1)。
输出：最长路径长度。
提示：先进行拓扑排序，然后按照拓扑序计算最长路径。
#include <iostream>
using namespace std;
int n, m, i, j, a, b, head, tail, ans;
int graph[100][100]; // 用邻接矩阵存储图
int degree[100]; // 记录每个结点的入度
int len[100]; // 记录以各结点为终点的最长路径长度
int queue[100]; // 存放拓扑排序结果
int main() {
cin >> n >> m;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
graph[i][j] = 0;
for (i = 0; i < n; i++)
degree[i] = 0;
for (i = 0; i < m; i++) {
cin >> a >> b;
graph[a][b] = 1;
(1) ;
}
tail = 0;
for (i = 0; i < n; i++)
if ( (2) ) {
queue[tail] = i;
tail++;
}
head = 0;
while (tail < n - 1) {
for (i = 0; i < n; i++)
if (graph[queue[head] ][i] == 1) {
(3) ;
if (degree[i] == 0) {
queue[tail] = i;
tail++;
}
}
(4) ;
}
ans = 0;
for (i = 0; i < n; i++) {
a = queue[i];
len[a] = 1;
for (j = 0; j < n; j++)
if (graph[j][a] == 1 && len[j] + 1 > len[a])
len[a] = len[j] + 1;
if ( (5) )
ans = len[a];
}
cout << ans << endl;
return 0;
}
设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做( )次比较。
| A． n2 |
B． n logn |
| C． 2n |
D． 2n-1 |
