UOJ Logo Universal Online Judge

UOJ

#84. 【UR #7】水题走四方

统计

今天是世界水日,著名的水题资源专家蝈蝈大臣发起了水题走四方活动,向全世界发放成千上万的水题。

蝈蝈大臣是家里蹲大学的教授,当然不愿意出门发水题啦!所以他委托他的助手欧姆来发。

助手欧姆最近做 UR #6 被狗狗传染了懒癌,当然不愿意出门发水题啦!所以他请来了高手 —— 地卜师。

全世界一共 $n$ 个城市,编号分别为 $1, \dots, n$。城市之间由双向道路相连,形成了一棵树。如果这棵树以 $1$ 为根,则除 $1$ 以外每个结点 $v$ 的父亲结点的编号 $p_v$ 满足 $p_v < v$。

由于地卜师掌握了克隆的核心科技,把自己完全复制了一份,他和他的分身一共两个地卜师一起出去执行任务。

现在,两个地卜师都站在 $1$ 号城市。地卜师可以沿道路行走,从一个城市移动到另一个城市。走一条道路需要耗时 $1$ 小时。当然,地卜师可以停留在某个城市不动。每到一个没有发放水题的城市,地卜师都会发水题。在一个城市里发水题的时间不计。

由于地卜师有强迫症,他沿道路移动时总是从一个城市移动到编号更大的城市。即总是从一个结点移动到它的儿子结点。地卜师和他的分身可以同时移动

但是地卜师这样好像不一定能经过所有的城市?没关系!地卜师会瞬移。如果某个时刻两个地卜师都在某个城市里(而不是在去某个城市的道路上),那么其中一个地卜师可以瞬移到另一个地卜师所在的城市。瞬移所需的时间不计。

现在地卜师想知道,要想顺利给每个城市都发放水题,最短需要多少个小时。

欧姆当然知道怎么计算啦!但是他想考考你。

输入格式

由于本题数据范围太大,为了方便读入,输入的是这棵树的括号序列表示。

第一行一个正整数 $n$。

第二行一个长度为 $2n$ 的字符串,仅包含 “(” 和 “)”。

下面给出了源代码,演示了怎样通过给出的括号序列求出每个结点的父亲。计算出了数组 pp[v] 的值即为结点 $v$ 的父亲的编号(特别地,p[1] 为 $0$)。你可以直接照抄。

C/C++ 代码

scanf("%d", &n);
scanf("%s", s);
v = 0;
tot = 0;
for (i = 0; i < n * 2; i++)
{
    if (s[i] == '(')
    {
        tot++;
        p[tot] = v;
        v = tot;
    }
    else
        v = p[v];
}

Pascal

readln(n);
readln(s);
v := 0;
tot := 0;
for i := 1 to n * 2 do
begin
    if s[i] = '(' then
    begin
        inc(tot);
        p[tot] := v;
        v := tot;
    end
    else
        v := p[v];
end;

输出格式

一行一个整数,表示最短需要多少时间完成任务,以小时为单位。

样例一

input

7
((()())(())())

output

4

explanation

计算可得:p[1] = 0, p[2] = 1, p[3] = 2, p[4] = 2, p[5] = 1, p[6] = 5, p[7] = 1

初始时两个地卜师都在 $1$,然后一个留在 $1$,另一个去 $5$ 号点 再去 $6$ 号点耗时 $2$ 小时,再瞬移回 $1$。然后两个地卜师一个去 $2$ 一个去 $7$,耗时 $1$ 小时,接着去 $7$ 的地卜师瞬移回 $2$,接着两个地卜师一个去 $3$ 一个去 $4$,耗时 $1$ 小时,共计 $4$ 小时。

样例二

input

1
()

output

0

样例三

见样例数据下载。

限制与约定

由于一些原因,本题使用捆绑测试。每个子任务有若干个测试点,分为 $4$ 个子任务,你只有通过一个子任务的所有测试点才能得到这个子任务的分数。

子任务 分值 $n$的规模
120$n \leq 12$
230$n \leq 1000$
330$n \leq 10^5$
420$n \leq 5 \times 10^6$

由于后一个子任务的数据范围总是包括了前一个子任务的数据范围,所以如果前一个子任务的测试点没有全部通过,后面的子任务都会被跳过并计后面的子任务 $0$ 分。

(骗分的小朋友考虑下造数据的人的感受好吗 TAT……)

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载