Trees

这是最普遍的情况, 从树中选取 \(m\) 个结点, 最大化它们的价值之和.

符合直觉地, 设 \(f_{u, i}\) 表示从以 \(u\) 为根的子树中选取了 \(i\) 个结点的最大价值之和. 转移是显然的:

这样转移时间复杂度即为 \(\Theta(nm)\).

考虑将重儿子设为链最长的那一个，剖分是简单的，可以做到 \(\Theta(n).\)

这样剖分有一些性质：

由于长链长度之和为 \(n\)，所以我们可以预处理每条链顶端节点的 \(l\) 级祖先，\(l\) 取遍不大于链长的所有整数。并且我们还可以存下每条链的所有节点，挂在链顶。

在一些问题中，我们只关心关键点的信息，同时我们需要维护他们之间的树形结构，于是可以想到将它们和它们之间的 \(\rm LCA\) 拉出来建一颗树，这棵树就被称作虚树。

不难发现这样一定是对的，并且设关键点数量为 \(k\)，则虚树内点数不超过 \(2k\)。

首先建虚树。

你在一颗树上旅行。

树由 \(n\) 个点，\(n - 1\) 条边构成，每条边的长度 \(w\) 是 \(1\) 或 \(2\)。

给定这棵树和 \(q\) 个询问，每个询问给出 \(u,v,l\)，请求出至少需要多少天。