#P1962. Corporative Network

Corporative Network

题目描述:

描述

一家规模非常庞大的公司正在发展其公司网络。起初,该公司的 NN 家企业(编号从 11NN)各自建立了自己的计算机与电信中心。不久之后,为了提升服务质量,公司开始将一些企业整合为集群,每个集群都由一个单独的计算机与电信中心提供服务,方式如下。公司会选择现有的一个中心 II(为集群 AA 提供服务)以及另一个集群 BB 中的一家企业JJ(不一定是该集群的中心),并用通信线路将它们连接起来。企业 IIJJ 之间线路的长度为 IJ(mod1000)\vert I - J\vert \pmod{1000}IIJJ差值的绝对值对10001000取模)。通过这种方式,两个旧集群合并成了一个新集群,由旧集群 BB 的中心来提供服务。不幸的是,每次合并之后,将企业与其服务中心相连的线路长度总和可能会发生变化,而终端用户希望知道新的总长度是多少。请编写一个程序来跟踪网络组织方面的变化,以便能够随时回答用户的问题。

输入:

你的程序必须能够处理多个测试用例。输入的第一行仅包含测试用例的数量 TT。每个测试用例将以企业的数量 NN 开头(5N200005 \leq N \leq 20000)。随后会有若干行(不超过200000200000行),每行包含以下命令之一:

E IE\ I —— 查询在当前时刻从企业 II 到其服务中心的路径长度;

I I JI\ I\ J —— 表示服务中心 II 与企业 JJ 建立了连接。测试用例以包含单词 OO 的一行作为结束标志。II 命令的数量少于 NN 个。

输出:

输出的行数应该与所有测试用例中 EE 命令的总数相同,且每行仅包含一个数字 —— 即所查询的将相应企业与其服务中心连接的线路长度总和。

输入数据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 年东南欧