PDF《IOI 2018 中国国家集训队集中培训》

'

呀,这时候想想,一株树还是不如一个人好.比如你,要是这样贴上去的话, 就能听到跳动的声音呢. 第5页共10 页IOI

2018 中国国家集训队集中培训 第四试 榕树之心(core) 【题目描述】 一棵榕树可以抽象成一棵 n 个结点的有根树,其中结点编号为

1 ? n,而1号点就 是根节点.初始时,树只有一号点,而心也在一号点.之后每一步,树都会长出一个新 结点,即某个和当前已经存在的某个结点相邻的结点被加入了树中,之后,心会沿着心 到新加结点的简单路径移动一步.这棵 n 个结点的树有很多种生长的顺序,不同的顺 序可能会导致最终心的位置不同.现在,Evan 和Lyra 想知道,哪些结点可能是心在 生长过程结束时停留的位置呢? 例如一棵大小为

4 的树,连边为 {<

1,

2 >

, <

1,

3 >

, <

1,

4 >

},我们有三种不同的生 长顺序可以让心分别停留在 2, 3,

4 号节点上: 最终停留在

2 号点: 1. 从1生长出 3,心从

1 移动到 3, 2. 从1生长出 4,心从

3 移动回 1, 3. 从1生长出 2,心从

1 移动到 2. 最终停留在

3 号点: 1. 从1生长出 2,心从

1 移动到 2, 2. 从1生长出 4,心从

2 移动回 1, 3. 从1生长出 3,心从

1 移动到 3. 最终停留在

4 号点: 1. 从1生长出 2,心从

1 移动到 2, 2. 从1生长出 3,心从

2 移动回 1, 3. 从1生长出 4,心从

1 移动到 4. 而我们可以证明,不存在任何一种可能的生长顺序使得心停留在

1 号点. 【输入格式】 从文件 core.in 中读入数据. 输入第一行一个两个正整数 W, T,分别表示子任务编号(在样例中 W = 0)和数 据组数,接下来是 T 组数据的描述,对于每组数据: 第一行一个正整数 n 表示树上结点的个数. 接下来 n ?

1 行,每行两个正整数 ai, bi,表示编号 ai, bi 的结点间有一条树边,保证ai bi 并且输入的 n ?

1 条边恰好构成了一棵树. 【输出格式】 输出到文件 core.out 中. 若输入的 W 不等于 3,对于每组数据输出一行一个长度为 n 的01 字符串,表示 编号为

1 ? n 的结点是否有可能是心最后所在的位置,若01 字符串对应位是

1 则表示 第6页共10 页IOI

2018 中国国家集训队集中培训 第四试 榕树之心(core) 可能,为0则表示不可能. 若输入的 W 等于 3,则对每组数据输出一个字符表示

1 号点的答案. 【样例

1 输入】

0 3

4 1

2 1

3 1

4 6

1 2

1 3

1 4

4 5

5 6

10 1

2 1

3 3

4 3

5 3

6 4

7 7

8 8

9 9

10 【样例

1 输出】

0111 000101

0000001010 【样例 2】 见选手目录下的 core/core2.in 与core/core2.ans. 第7页共10 页IOI

2018 中国国家集训队集中培训 第四试 榕树之心(core) 【提示】 这是一道不太难的题. 【子任务】 Subtask 1[10pts] T ≤ 50;

n ≤ 15. Subtask 2[10pts] T ≤ 20;

n ≤

105 .除了

1 号点之外,每个点度数(包括父亲)不超过 2. Subtask 3[10pts] T ≤ 200;

n ≤ 100.只输出一个字符表示

1 号点答案,即保证

1 号点答案正确即可. Subtask 4[35pts] T ≤ 20;

n ≤

103 . Subtask 5[35pts] T ≤ 20;

n ≤

105 . 第8页共10 页IOI

2018 中国国家集训队集中培训 第四试 某位歌姬的故事(rmq) 某位歌姬的故事(rmq) 【题目描述】 IA 是一名会唱歌的女孩子. IOI2018 就要来了,IA 决定给参赛选手们写一首歌,以表达美好的祝愿.这首歌一 共有 n 个音符,第i个音符的音高为 hi.IA 的音域是 A,她只能唱出