题解：AT_abc394_f [ABC394F] Alkane
Beacon_wolf
·
·
题解
树是连通的，从任意结点出发都能访问所有结点，而题目要求至少有一个度数为 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[u] = 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 一下就行。