题面

小C喜欢步行，只有缓慢的步行，小C才能沉浸于其中，享受旅途中那些美好的瞬间。
小C来到了一座新的城市生活，这座城市可以看成 $n$ 个点，$n-1$ 条长度为 $1$ 的无向边连接的连通图，也就是说这个城市的结构是一棵树。小C计划在这个城市旅行，他对这个城市的每一个节点都进行了初步的了解，并制定了一个旅行计划，他按照自己的兴趣等因素，为每一个节点设定了游览次数 $v_i$，表示他计划在第 $i$ 个节点游览多少次。
在这之后，小C想要找出一个游览序列。游览序列是一个长度为 $S=\sum v_i$ 的序列，对于 $i∈[1,n]$ ，$i$ 在序列中出现 $v_i$ 次，设这个序列为 $A$ 。确定序列后小C将会沿着 $A_1,A_2,…,A_S$ 的顺序步行游览，每次从一个点走最短路径到下一个点，并最终从 $A_S$ 返回 $A1$ ，游览序列中相邻的两位以及 $A_S$ ，A可以相同，这个时候小C的步行距离为0。小C喜欢步行，因此他希望他的总步行距离尽可能长。小C发现这一座城市还会时常发生交通管制事件，在这样的情况下，一条原有的道路会无法通行，还会有一条临时道路出现，管制过程中这座城市依旧连通。小C会告诉你m次这样的事件，希望你告诉他在这m种管制情况下，他的最长步行距离分别是多少。然而小C的信息也有可能是错的，例如无法通行的道路不存在，或者管制后的城市不连通，这时你需要告诉他这条信息是错误的。