#P11711. 「KTSC 2020 R2」列车的移动

「KTSC 2020 R2」列车的移动

题目背景

请使用 C++17 或 C++20 提交本题

你需要在程序开头加入如下代码:

#include <vector>

void init(int N, std::vector<int> X, std::vector<int> Y);

long long train(std::vector<int> Z);
  

题目译自 2020년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T4「 열차의 이동

题目描述

调车场是连接或分离列车车厢并进行维护和保养的地方。调车场中有可以移动列车的轨道。我们将用图来表示轨道上列车车厢的位置。图中的每条边表示列车的一个车厢所在的位置,因此列车在图中表示为一条路径。在这条路径上,所有的顶点和边都必须不同。特别地,问题中给出的图总是树形结构。

列车可以沿着轨道移动。列车的移动是分阶段进行的,每个阶段列车的一端车厢移动到相邻的另一条边上。具体来说,对于表示列车的路径 PP,一次移动的结果是将 PP 的一端顶点和相邻的 PP 之外的边和顶点添加到 PP 中,并将另一端的顶点和边从 PP 中移除(见图 1)。注意,每个阶段路径的长度保持不变。

给定初始和最终列车位置的长度为 mm 的路径 PPQQ。路径的长度是路径中包含的边的数量。这里,路径 PPQQ 之间没有任何共享的边。换句话说,PPQQ 没有同时经过的边。我们需要将路径 PP 移动到最终成为路径 QQ。此时,需要找到最少的移动步数。

给定包含 nn 个顶点的树 TT 以及初始和最终列车位置的长度为 mm 的路径 PPQQ,编写一个程序,检查是否可以将 PP 移动到 QQ,如果可以,输出最少的移动步数。

例如,在图 2 中,给定长度为 22 的两个路径 PPQQ,它们没有任何共享的边。可以看到,从路径 PP 移动到路径 QQ 需要 55 步,这是最少的移动步数。

你需要为管理员实现以下两个函数:

void init(int n, vector<int> X, vector<int> Y);

  • 该函数在程序开始时调用一次。树的顶点数量为 nn,顶点编号从 11nnXY 是大小为 n1n-1vector,表示树的每条边为 (X[i],Y[i])(X[i], Y[i])

long long train(vector<int> Z);

  • 参数 Z 是大小为 44vector,表示初始路径 PP 的两个端点 Z[0]Z[1],以及最终路径 QQ 的两个端点 Z[2]Z[3]。函数返回将 PP 移动到 QQ 的最少步骤数。如果无法移动,则返回 -1

这些函数应按照上述描述工作。当然,你可以创建其他函数并在内部使用。提交的代码不应执行输入输出操作或访问其他文件。

输入格式

评测程序按以下格式读取输入:

  • 11 行:nqn\,qnn 表示树的顶点数量,树的顶点编号从 11nnqq 表示查询的数量
  • 接下来的 n1n-1 行:xyx\,y,表示树的一条边 (x,y)(x, y)1xyn1 \le x \neq y \le n
  • 接下来的 qq 行:abcda\,b\,c\,d,表示初始路径 PP 的两个端点 aabb,最终路径 QQ 的两个端点 ccdd

输出格式

评测程序将输出函数 train 的返回值。如果无法移动,则输出 -1

11 2
1 2
3 2
4 3
4 5
6 5
8 4
7 8
8 9
10 9
11 10
3 5 7 4
3 6 7 10
3
7

提示

样例说明 #1

以下是样例中函数调用及其结果的顺序:

函数调用 返回值
init(11, {1,3,4,4,6,8,7,8,10,11}, {2,2,3,5,5,4,8,9,9,10})
train({3,5,7,4}) 33
train({3,6,7,10}) 77

数据范围

对于所有输入数据,满足:

  • 3n2.5×1053 \leq n \leq 2.5\times 10^5
  • 1q2.5×1051 \leq q \leq 2.5\times 10^5
  • 所有查询中路径 PP 的长度总和 106\leq 10^6

详细子任务附加限制及分值如下表所示。

子任务 分值 约束
11 1111 n80,q80n \leq 80, q \leq 80
22 1818 路径 PP 的长度 2\leq 2
33 3434 路径 PP 的长度 100\leq 100,所有路径 PP 的长度总和 2.5×105\leq 2.5\times 10^5
44 3636 n1000,q1000n \leq 1000, q \leq 1000
55 5151 无附加限制

本题满分为 150150 分。