#2133. 画树
画树
画树
题目描述
第一试画树(paint) IOI2026 中国国家队选拔 画树(paint) 【题目描述】 小F 在美术课上学习了如何画树。他画了一棵n 个结点的树T,结点编号为1 ∼n。 由于对当前这棵树不太满意,小F 打算使用k 对一一配对的铅笔与橡皮来涂改它。 初始时,他把每对铅笔与橡皮放置在树的某个结点上。具体地,对于1 ≤i ≤k,记铅笔 所在的结点为pi,橡皮所在的结点为ei,则初始时pi = ei。在任意时刻,同一个结点上 可以同时放置多支铅笔与多只橡皮。 每次涂改时,小F 将首先选择一对铅笔与橡皮。设小F 选择的是第t (1 ≤t ≤k) 对铅笔与橡皮,则他将按以下步骤进行涂改:
- 选择.任.意一个结点x (1 ≤x ≤n),将铅笔移动至结点x,并绘制移动形成的边, 即在pt 与x 之间添加一条边,然后令pt ←x;
- 选择一个与et .有.边.直.接.相.连的结点y (1 ≤y ≤n)(可以是上一步中新绘制的 边),将橡皮移动至结点y,并擦除移动经过的边,即删除et 与y 之间的边,然 后令et ←y。 当然,小F 需要保证.每.次.涂.改.后.得.到.的.图.仍.然.是.一.棵.树。 小F 希望使用尽可能少的铅笔与橡皮对将树T 涂改为另一棵树T ′。你需要帮助小 F 构造一组涂改的方案。具体地,你需要确定铅笔与橡皮对的数量k,并且指定每对铅 笔与橡皮的初始位置pi, ei (1 ≤i ≤k, pi = ei),再构造一组涂改序列(t, x, y) (1 ≤t ≤ k, 1 ≤x, y ≤n),使得依次执行这些涂改后,树T 能被转变为树T ′。 【实现细节】 .选.手.不.需.要,.也.不.应.该.实.现main .函.数。 选手需要确保提交的程序包含头文件paint.h,即在程序开头加入以下代码: #include "paint.h" 1 选手需要在提交的程序源文件中实现以下函数: void paint(int n, std::vector u, std::vector v); 1 • n 表示树T 的结点个数。 • 对于0 ≤i < n −1,ui, vi 表示树T 的一条边。 • 对于n −1 ≤i < 2n −2,ui, vi 表示树T ′ 的一条边。 • 对于每个测试点,该函数会被交互库调用.恰.好t .次。 选手可以通过调用以下函数设置铅笔与橡皮对的数量与每对铅笔与橡皮的初始位 置: void setting(int k, std::vector p); 1 第6 页 共14 页 第一试画树(paint) IOI2026 中国国家队选拔 • k 表示使用的铅笔与橡皮对的数量。选手需要保证0 ≤k ≤2n。 • 对于0 ≤i < k,pi 表示第i + 1 对铅笔与橡皮的初始位置。选手需要保证p 的长 度为k,且对于所有0 ≤i < k,均有1 ≤pi ≤n。 • 选手需要保证交互库每次调用paint 时,.恰.好.调.用.了.一.次.该.函.数。 选手可以通过调用以下函数进行一次涂改: void alter(int t, int x, int y); 1 • t, x, y 分别表示选择的铅笔与橡皮对的编号与结点的编号,具体含义如【题目描 述】中所示。选手需要保证1 ≤t ≤k,1 ≤x, y ≤n,且.涂.改.后.得.到.的.图.仍.然.是 .一.棵.树。 • 选手需要保证交互库每次调用paint 时,调用该函数的次数不超过105,且所有 该函数的调用.均.在.调.用setting .函.数.之.后。 .注.意:.在.任.何.情.况.下,.交.互.库.运.行.所.需.时.间.均.不.会.超.过0.2 .秒,.所.用.内.存.为.固.定.大 .小,.且.均.不.超.过64 MiB。 【测试程序方式】 .试.题.目.录.下.的grader.cpp .是.交.互.库.参.考.实.现,.最.终.测.试.时.所.用.的.交.互.库.实.现.与.该 .参.考.实.现.有.所.不.同,.因.此.选.手.的.解.法.不.应.该.依.赖.交.互.库.实.现。 选手可以在本题目录下使用如下命令编译得到可执行程序: g++ grader.cpp paint.cpp ‐o paint ‐O2 ‐std=c++14 ‐static 1 对于编译得到的可执行程序: • 可执行文件将从.标.准.输.入读入以下格式的数据: – 输入的第一行包含一个正整数t,表示测试数据组数。 – 接下来依次为每组测试数据,对于每组测试数据: ∗第一行包含一个正整数n,表示树T 的结点个数。 ∗第i + 1 (1 ≤i ≤n −1) 行包含两个正整数ui, vi,表示树T 的一条边。 i,表示树T ′ 的一条边。 ∗第i + n (1 ≤i ≤n −1) 行包含两个正整数u′ i, v′ • 可执行文件将输出以下格式的数据至.标.准.输.出: – 对于每组测试数据: ∗第一行包含两个非负整数k, m,分别表示使用的铅笔与橡皮对的数量与 涂改序列的长度。 ∗第二行包含k 个正整数p1, p2, . . . , pk,分别表示每对铅笔与橡皮的初始 位置。 ∗第i + 2 (1 ≤i ≤m) 行包含三个正整数t, x, y,分别表示第i 次涂改选 择的铅笔与橡皮对的编号与结点的编号。 第7 页 共14 页 第一试画树(paint) IOI2026 中国国家队选拔 【样例1 输入】 2 1 5 2 2 3 3 3 1 4 5 1 5 5 4 6 1 4 7 2 3 8 3 1 9 5 3 10 5 11 4 2 12 1 3 13 5 1 14 1 2 15 2 1 16 3 5 17 3 1 18 4 5 19 【样例1 输出】 1 3 1 1 2 1 4 5 3 1 5 4 4 1 3 5 5 2 2 6 4 5 7 1 5 2 8 2 3 1 9 【样例1 解释】 该样例共包含两组测试数据。 第8 页 共14 页 第一试画树(paint) IOI2026 中国国家队选拔 对于第一组测试数据,树T 包含边{(1, 3), (3, 2), (1, 5), (5, 4)},树T ′ 包含边{(1, 4), (2, 3), (3, 1), (5, 3)}。一种可行的涂改方案如下: • 初始时,共有1 对铅笔与橡皮放置在结点1。 • 第一次涂改选择x = 4,y = 5,添加边(1, 4),删除边(1, 5),得到的树包含边 {(1, 3), (3, 2), (5, 4), (1, 4)},此时p1 = 4,e1 = 5; • 第二次涂改选择x = 5,y = 4,添加边(4, 5),删除边(4, 5),此时p1 = 5,e1 = 4; • 第三次涂改选择x = 3,y = 5,添加边(5, 3),删除边(4, 5),得到的树包含边 {(1, 3), (3, 2), (1, 4), (5, 3)},即为树T ′。 【附加文件说明】 在附加文件中:
- grader.cpp 是提供的交互库参考实现。
- paint.h 是头文件,选手不用关心具体内容。
- template_paint.cpp 是提供的示例代码,选手可参考并实现自己的代码。 【子任务】 对于所有测试数据,均有: • 5 ≤n ≤200; • 对于所有1 ≤i < n,均有1 ≤ui, vi ≤n,且所有的边构成了一棵树; • 对于所有1 ≤i < n,均有1 ≤u′ i, v′ i ≤n,且所有的边构成了一棵树; • T 和T ′ 均在所有n 个结点的树中.独.立.均.匀.随.机生成。 本题共有20 个测试点,每个测试点均包含恰好10 组测试数据。 对于第i (1 ≤i ≤n) 个测试点,所有测试数据均满足n = 10i。 【评分方式】 .注.意: • 选手不应当通过非法方式获取交互库的内部信息,如直接与标准输入、输出流进 行交互。此类行为将被视为作弊; .最.终.的.评.测.交.互.库.与.样.例.交.互.库.的.实.现.不.同。 • .本.题.首.先.会.受.到.和.传.统.题.相.同.的.限.制,例如编译错误会导致整道题目得0 分,运行 时错误、超过时间限制、超过空间限制等会导致相应测试点得0 分等。选手只能在程序 中访问自己定义的变量以及交互库给出的变量,尝试访问其他地址空间将可能导致编译 错误或运行错误。 每次调用paint 函数时,若setting 函数或alter 函数调用不合法,或alter 函数调用次数超过105,或返回时树T 未被转变为树T ′,则相应测试点得0 分。 在上述条件基础上: 第9 页 共14 页 第一试画树(paint) IOI2026 中国国家队选拔 • 对于每组测试数据,设kmin 表示使用的铅笔与橡皮对数的最小值,则获得5 · 0.97k−kmin · 0.99max(⌈m/2000⌉−5,0) 分。 • 对于每个测试点,程序得到的分数为该测试点包含的所有测试数据的得分的.最.小 .值。 第10 页 共14 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2
5
2 3
3 1
5 1
5 4
1 4
2 3
3 1
5 3
5
4 2
1 3
5 1
1 2
2 1
3 5
3 1
4 5
1 3
1
1 4 5
1 5 4
1 3 5
2 2
4 5
1 5 2
2 3 1