#P10554. [2021年联测]烷烃命名

    ID: 9671 传统题 2000ms 512MiB 尝试: 5 已通过: 1 难度: 6 上传者: 标签>图论字符串CF2000树形DPDFS模拟直径树的重心

[2021年联测]烷烃命名

烷烃命名(name)

【题目描述】

给定一个链烃,按照系统命名法给其命名。

如果你不了解什么是链烃或系统命名法,请参见提示。

【输入格式】

从标准输入读入。

第一行一个整数nn,表示碳原子的个数。

接下来n−1n-1 行,每行两个整数u,vu,v表示编号为uu和vv的碳原子之间由一个碳-碳单键连接。

【输出格式】

输出到标准输出。

第一行输出三个数,分别表示主链的长度ll,主链的两个端点u,vu,v。主链可能不唯一, 任意输出一个合法的即可,详见提示。

接下来nn行,第ii行先输出一个kik_{i},表示命名结果中i−i- 烷基的数量。接着升序输出每个i−i- 烷基的位置,位置从 11 开始编号。

提示:输出的应当是主链上的位置,而非碳原子的标号。

【样例 1 输入】

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

【样例 1 输出】

6 6 7
2 2 4
1 3
0
0
0
0
0
0
0
0

【样例 1 解释】

原题示意图

图 1: example-1

如上图所示,路径 (6,7)(6,7) 是符合条件的一条主链。当其作为主链时,{1},{10}\{1\},\{10\} 分别为位置 2,42,4 上的甲基,{8,9}\{8,9\} 为位置 33 上的乙基。

同样合法的主链还包括:(1,6)(1,6)。而 (6,9)(6,9) 虽然长度也为 66,但是不是一条合法的主链。

【样例 2 输入】

8
1 2
2 3
3 4
4 5
2 6
3 7
7 8

【样例 2 输出】

5 8 6
1 2
1 3
0
0
0
0
0
0

【样例 2 解释】

原题示意图

图 2: example-2

如上图所示,以上烷烃主链有 (6,8),(5,6),(1,8),(1,5)(6,8),(5,6),(1,8),(1,5) 四种选法,都是合法的。 图中所示的为 (6,8)(6,8) 这条主链,按照这条主链可能得到 2-甲基-3-乙基戊烷或者 4-甲基-3-乙基戊烷两种命名结果。根据最低系列原则,应当取“2-甲基-3-乙基戊烷”作为命名结果,对应输出如样例所示。

【样例 3 输入】

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

【样例 3 输出】

6 8 13
2 2 4
1 3
1 3
0
0
0
0
0
0
0
0
0
0

【样例 4】

见 /ex_name4.in 与 /ex_name4.out。

【测试点约束】

对于所有测试点,1≤n≤5×1051\le n\le 5\times 10^{5}。

本题采用捆绑评测,你在一个子任务中的得分是该子任务中所有测试点得分的最小

值。

每个子任务的具体限制见下表:

子任务编号 n≤n\le 分数
11 300300 17
2 30003000 24
33 5×1055\times 10^{5} 59

【计分规则】

• 如果你的答案中,选取的主链不合法,且长度与合法的主链长度不同,则不能获得任何分数。提示信息为 Wrong Answer[1].

• 如果你的答案中,选取的主链不合法,但是长度与合法的主链长度相同,可以获得该测试点 1212% 的分数。提示信息为 Wrong Answer[2].

• 如果你的答案中,选取的主链合法,但是对应的命名结果和该主链对应的命名结果不符的,可以获得该测试点 3535% 的分数。其中如果某烷基数量不正确。提示信息为 Wrong Answer[3];若是该烷基所在的位置不对,提示信息为 Wrong Answer[4].

• 如果你的答案完全正确,可以获得全部分数。提示信息为 Accepted。

【提示】

Q1Q_{1}:什么是链烃?

A1A_{1}:链烃就是只由碳原子和氢原子组成,所有的碳之间都由碳-碳单键连接且不形成环的有机化合物。当一个碳只和不足 44 个碳原子有共价键时,剩余共价键由碳-氢键补足, 我们无需过多考虑。在本题中,我们可以简单地认为碳原子连接形成一棵每个点度数不超过 44 的无标号树。

Q2Q_{2}:什么是系统命名法?

A2A_{2}:有机化合物种类繁多,数目庞大,即使同一分子式,也有不同的同分异构体。中国 1980 年《有机化学命名原则》增订本规定了链烃的系统命名法的命名规则。

命名链烃时,首先要确定主链。确定主链的原则是:

  1. 首先考虑链的长短,长的优先。

  2. 若有两条或多条等长的最长链时,则根据支链的数目来确定主链,多的优先。为方便描述,这里我们将支链的数量定义为“不在主链上,且与主链上的碳原子由共价键直接连接的碳原子个数”。如果你了解支链的严谨定义,不难发现这两种描述是等价的。

  3. 若仍无法分出哪条链为主链,则依次考虑下面的原则,侧链位次小的优先,各侧链碳原子数多的优先,侧分支少的优先。

主链确定后,要根据最低系列原则 (lowest series principle) 对主链进行编号。最低系列原则的内容是:使取代基的号码尽可能小,若有多个取代基,逐个比较,直至比出髙低为止。最后,根据有机化合物名称的基本格式写出全名。

为降低题目难度,且因其在实际中应用较少,我们不考虑主链选取中第 3 条的内容。 我们认为如果一条链是这颗链烃中最长的一条碳链,并且在相同长度的碳链中,其支链数量是能达到的最多的,那么它就是一条合法的主链。一个链烃可能存在多条合法的主链,任意输出一条即可,但接下来的命名必须与这条选好的主链相对应。 在本题中,最低系列原则我们如下定义:

  1. 如果对于一条主链有多种可能导致命名结果不同的选取取代基的方法,那么我们要求甲基多者优先;

  2. 如果甲基数量相同,对于所有甲基的位置升序排列而成的序列,字典序小者优先;

  3. 如果以上仍相同,则同理依次比较乙基、丙基......的情况,直到不同为止。