拨打电话 - 题目

题目描述

用一棵有根树 $T$ 表示简化的电话网络。在 $T$ 中，每个叶结点对应一个具体的通话终端，而每个内部结点表示可以处理通话请求的交换节点。每个通话终端都有一个自己的号码 $a_i$，但是为了让交换节点正确处理通话请求，通常需要在原始号码的前面加上若干前缀编号，用于指明被呼叫者在电话网络中所处的位置。例如，从中国大陆的其它地区拨打北京市的固定电话，则需要在前面按顺序加上长途冠码 0 及北京市区号 10，才能正确地拨通对应的电话。在 $T$ 中，从通话终端 $u$ 向通话终端 $v$ 拨打电话时，正确的电话号码应通过沿着在 $T$ 上从 $u$ 到 $v$ 的最短路，按顺序连接各交换节点相应前缀号（即最靠近 $u$ 的交换节点的前缀号应在最前，最靠近 $v$ 的交换节点的前缀号应在最后）后，加上 $v$ 本身的号码得到。

在 $T$ 中，根据发出请求的通话终端、接受请求的通话终端与交换节点的关系，每个交换节点各有 $3$ 种可能为空的前缀号，分别为：

从该交换节点 $v$ 在 $T$ 中对应子树内向子树外拨打电话时需要加的前缀号 $b_v$，如从中国大陆拨打其它国家或地区的电话时需加国际冠码 00；
从该交换节点 $v$ 在 $T$ 中对应子树外向子树内拨打电话时需要加的前缀号 $c_v$，如从其它国家或地区向中国大陆拨打电话时需加中国大陆的国际区码 86；
从该交换节点 $v$ 在 $T$ 中任意一子结点（子结点可能为某一通话终端，也可能是其它交换节点，后同）向 $v$ 发出请求，$v$ 需要将该请求转发给另外一子结点进行处理时的需要加的前缀号 $d_v$，如从中国大陆的其它地区拨打北京市的固定电话 ABCDEFGH，需要使用长途冠码 0，对应电话号码为 010-ABCDEFGH；而从其它国家或地区拨打北京市的同一电话，则只需在国际冠码之后拨打 86-10-ABCDEFGH，不需要使用长途冠码 0。

现在给出 $T$ 中若干个通话请求，每个请求由拨出结点和该请求在该结点拨打的电话号码组成，请判断拨打的电话号码是否对应唯一的通话终端。如果是，请求出该通话终端；否则，请求出与该电话号码对应的通话终端数量。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $n, q$，表示电话网络 $T$ 的结点数和通话请求的数量。保证 $2\le n\le 10^5$，$1\le q\le 10^5$。

接下来 $n$ 行，每行输入两个非负整数和一个字符串 $f_i$，$t_i$，$s_i$，分别由一个空格隔开，描述 $T$ 的第 $i$ 个结点。其中，$f_i>0$ 时表示结点 $i$ 在 $T$ 上的父结点编号，$f_i=0$ 表示结点 $i$ 是 $T$ 的根；$t_i\in\{0,1\}$ 表示结点 $i$ 是否为叶结点，

如果 $t_i=1$，则结点 $i$ 为叶结点，此时 $s_i$ 是仅由字符 0 至 9 构成的非空字符串，表示结点 $i$ 的原始电话号码 $a_i$；
如果 $t_i = 0$，则结点 $i$ 为内部交换节点，此时 $s_i$ 包含三个由单个 / 字符隔开的仅由字符 0 至 9 构成的字符串（可能为空），分别为前缀号 $b_i$，$c_i$ 和 $d_i$。

保证 $0\le f_i < i$，所有叶结点的 $a_i$ 及所有内部 $b_i, c_i, d_i$ 的总长不超过 $3\times 10^6$。

接下来 $q$ 行，每行输入一个正整数 $p_i$ 和一个仅包含字符 0 至 9 的非空字符串 $r_i$，表示在结点 $p_i$ 拨打电话号码为 $r_i$ 的通话请求。保证 $p_i$ 对应叶结点，$\sum_{i=1}^q \left|r_i\right| \le 3\times10^6$。

输出格式

输出到标准输出。

对每个通话请求输出一行。如果拨打的电话号码对应唯一的通话终端，输出 1 x，其中正整数 $x$ 是该通话终端的编号；否则，输出 0 y，其中非负整数 $y$ 是匹配的通话终端的数量。

样例

输入

24 10
0 0 //
1 0 00/86/0
2 0 /10/
3 1 62793001
3 1 62770334
3 1 62783054
3 1 62757487
3 1 62562503
2 0 /20/
9 1 88331234
9 1 83561784
1 0 001/852/
12 1 23587000
1 0 010/81/0
14 0 /3/
15 0 /5841/2
16 1 4111
16 1 7926
14 0 /6/
19 0 /6879/
20 1 4508
20 1 4421
19 0 /6850/
23 1 6618
7 62793001
7 01062793001
10 62770334
10 01062770334
8 02083561784
10 0085223587000
17 27926
17 0668794508
21 4421
21 68506618

输出

解释

为方便理解题意，该样例使用了实际存在的电话号码。其表示的电话网络见下图。

- 第一个询问的通话请求是从北京大学计算机学院至清华大学后勤综合服务热线/校内查号台。因为这两个结点的父结点均为结点 $3$（对应北京市），且父结点 $d_3=\varepsilon$，所以直接拨打对应电话即可。第二个询问为第一个询问加上区号的版本，在本题中认为该询问的电话号码无法拨通。

第四个询问为香港科技大学（广州）向清华大学招生办公室发出通话请求。由于两个通话终端的父结点不同，拨打电话时应加上前缀 $b_9 + d_2 + c_3=$ 010。第三个询问与第四个询问类似，但是没有加上前缀，故无法拨通。
第五个询问为中国计算机学会致电广东省计算机学会，计算应拨打电话号码的方式为 $b_3 + d_2 + c_9 + a_{11}$。
第六个询问为从香港科技大学（广州）向香港科技大学计算机科学与工程系（Department of Computer Science and Engineering）发出通话请求。拨打电话时，应先按顺序拨打中国大陆的国际冠码 $b_2=$ 00 和中国香港的国际区码 $c_{12}=$ 852，然后再键入原始电话号码 $a_{13}$（完整的计算方法为 $b_9 + b_2 + d_1 + c_{12} + a_{13}$）。
第七个询问为从东京大学研究生院计算机科学专业办公室拨至情报理工学系研究科招生办公室。由于本乡校区的内部电话需要在 $4$ 位电话之前加上 $d_{16}=$ 2，正确的电话号码为 2 $+$ 7926 $=$ 27926。
第八个询问为东京大学研究生院计算机科学专业办公室向大阪大学研究生院信息科学研究科办公室拨打电话。拨打电话时，应先后加上长途冠码 $d_{14}=$ 0、大阪的区号（市外局番）$c_{19}=$ 6 和吹田校区所属的子区域区号（市内局番）$c_{20}=$ 6879。应拨打的电话号码的完整表达式为 $b_{16}+b_{15}+d_{14}+c_{19}+c_{20}+a_{21}$。
第九个询问为从大阪大学研究生院信息科学研究科办公室拨打电话给同样位于吹田校区的生命机能研究科。$d_{20}=\varepsilon$ 意味着吹田校区的内部电话不需要加前缀，可以直接拨打对应 $4$ 位电话号码。
第十个询问为从大阪大学研究生院信息科学研究科办公室向大阪大学信息科学系的办公室拨打电话。由于本科的信息科学系位于丰中校区，所以需要在原始电话号码前加上丰中校区对应的子区域区号（市内局番）$c_{23}=$ 6850（实际拨打电话时，也可以使用丰中校区的内部电话前缀 172，但这不在本题考虑范围之内）。

样例

输入

输出

解释

从结点 $2$ 的子树中拨打 0100，可以匹配到结点 $3$ 和结点 $5$；拨打 0101，可以匹配到结点 $4$ 和结点 $6$。因为一个结点播出的电话号码不能匹配自己，所以只有第二个询问和第六个询问拨出的电话号码对应唯一的通话终端。

样例三

见下载目录下的 ex_3.in 与 ex_3.ans。

QOJ.ac

QOJ

# 8755. 拨打电话

题目描述

输入格式

输出格式

样例

输入

输出

解释

样例

输入

输出

解释

样例三