题解：ABC394F - Alkane

Atcoder
LuoguBlog
题目描述

给定一棵包含 \(N\) 个顶点的无向树 \(T\)。顶点编号为 \(1, 2, \ldots, N\)，第 \(i\) 条边连接顶点 \(A_i\) 和顶点 \(B_i\)。
定义满足以下两个条件的图为烷烃：

• 该图是一棵无向树
  
• 所有顶点的度数为 \(1\) 或 \(4\)，且至少存在一个度数为 \(4\) 的顶点
  

请判断 \(T\) 中是否存在满足烷烃定义的子图。若存在，求此类子图的顶点数的最大值；否则输出 \(-1\)。
输入格式

输入通过标准输入按以下格式给出：

\(N\)
\(A_1\) \(B_1\)
\(A_2\) \(B_2\)
\(\vdots\)
\(A_{N-1}\) \(B_{N-1}\)

输出格式

若存在满足烷烃定义的子图，输出其顶点数的最大值；否则输出 \(-1\)。
输入输出样例 #1

输入 #1

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

复制代码

输出 #1

1. 8

复制代码

输入输出样例 #2

输入 #2

1. 7
2. 1 2
3. 1 3
4. 2 4
5. 2 5
6. 3 6
7. 3 7

复制代码

输出 #2

1. -1

复制代码

输入输出样例 #3

输入 #3

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

复制代码

输出 #3

1. 11

复制代码

说明/提示

约束条件

• \(1 \leq N \leq 2 \times 10^5\)
  
• \(1 \leq A_i, B_i \leq N\)
  
• 输入的图是一棵无向树
  
• 所有输入值为整数
  

样例解释 1

选取顶点 \(1, 2, 3, 4, 6, 7, 8, 9\) 及边 \((1,2)\)、\((2,3)\)、\((3,4)\)、\((2,6)\)、\((2,7)\)、\((3,8)\)、\((3,9)\) 构成的子图满足烷烃条件。其中顶点 \(2\) 和顶点 \(3\) 的度数为 \(4\)，其余顶点度数为 \(1\)，因此顶点数的最大值为 \(8\)。
Solution

树是连通的，从任意结点出发都能访问所有结点，而题目要求至少有一个度数为 \(4\) 的结点，所以我们不妨找一个度数为 \(4\) 的结点先当做根。
定义 \(dp_u\) 为以 \(u\) 为根的最大烷烃大小，\(T\) 为给定的树，\(u\) 为树中的一个结点，\(children_u\) 为 \(u\) 的子结点集合。
因为我们要使结点数尽量多，所以要贪心地取答案最大的几个子结点的答案。
设 \(u\) 的子节点集合为 \(\operatorname{children}(u)\)，\(k = |\operatorname{children}(u)|\)。
将 \(\{ dp[v] \mid v \in \operatorname{children}(u) \}\) 从大到小排序，得到 \(s_1 \ge s_2 \ge \cdots \ge s_k\)。
定义分段函数 \(f(k)\)：

\[f(k) = \begin{cases}1 + s_1 + s_2 + s_3, & k \ge 3 \\[2ex]1, & k < 3\end{cases}\]
则：

\[dp = f(k)\]
对于每个节点 \(u\)，考虑它作为根结点的情况：
定义分段函数 \(g(k)\)：

\[g(k) = \begin{cases}1 + s_1 + s_2 + s_3 + s_4, & k \ge 4 \\[2ex]1 + s_1, & k = 1 \\[2ex]0, & k = 0\end{cases}\]
则答案：

\[ans = \max_{u} g(k)\]
其中 \(k = |\operatorname{children}(u)|\)。
dfs 一下就行。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！