题解：AT_abc394_f [ABC394F] Alkane

树是连通的，从任意结点出发都能访问所有结点，而题目要求至少有一个度数为 \(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 一下就行。