#P1962. Corporative Network
Corporative Network
题目描述:
描述
一家规模非常庞大的公司正在发展其公司网络。起初,该公司的 家企业(编号从 到 )各自建立了自己的计算机与电信中心。不久之后,为了提升服务质量,公司开始将一些企业整合为集群,每个集群都由一个单独的计算机与电信中心提供服务,方式如下。公司会选择现有的一个中心 (为集群 提供服务)以及另一个集群 中的一家企业(不一定是该集群的中心),并用通信线路将它们连接起来。企业 和 之间线路的长度为 (与差值的绝对值对取模)。通过这种方式,两个旧集群合并成了一个新集群,由旧集群 的中心来提供服务。不幸的是,每次合并之后,将企业与其服务中心相连的线路长度总和可能会发生变化,而终端用户希望知道新的总长度是多少。请编写一个程序来跟踪网络组织方面的变化,以便能够随时回答用户的问题。
输入:
你的程序必须能够处理多个测试用例。输入的第一行仅包含测试用例的数量 。每个测试用例将以企业的数量 开头()。随后会有若干行(不超过行),每行包含以下命令之一:
—— 查询在当前时刻从企业 到其服务中心的路径长度;
—— 表示服务中心 与企业 建立了连接。测试用例以包含单词 的一行作为结束标志。 命令的数量少于 个。
输出:
输出的行数应该与所有测试用例中 命令的总数相同,且每行仅包含一个数字 —— 即所查询的将相应企业与其服务中心连接的线路长度总和。
输入数据1
1
4
E 3
I 3 1
E 3
I 1 2
E 3
I 2 4
E 3
O
输出数据1
0
2
3
5
来源:
2004 年东南欧