题目链接

读入$n$个整数，选取其中若干个数，最多连续取$k$个，求取到数字和的最大值

$1\le k \le n \le 100000$

感谢@oy 的贡献

题目链接

$n$个点的树上有$m$条路径$(S_i, T_i)$，每条路径上各有一个人从$S_i$跑到$T_i$。他们在第$0$时刻同时跑，每秒能跑一条边。回答$n$个询问，询问恰好在第$W_i$时刻到达节点$i$的人数。

$1 \le n \le 300000,1 \le m \le 300000 $

感谢@tth37 的贡献

题目链接

给定一棵$n$个节点的树，每个节点上有一个权值。对于$m$次询问，需要输出$u$到$v$的最短路径上第$k$小的点权。

$1\le n\le 100000,1 \le m\le 100000$

感谢@tth37 的贡献

题目链接

背包类树形dp。本题需要运用分组背包模型。

首先定义状态：$f[u][i]$表示以$u$为根的子树上，选择$i$个用户时的最大利润。由于电视公司可能亏本，因此$f$数组应赋极小初值。

可以将选择的用户个数看作背包的容量维度，将获得的利润看作背包的价值维度。可以设计出如下的状态转移：
$$
f[u][i]=\max_{v\in son(u)}{f[u][i-j]+f[v][j]-w}
$$
其中，$v$为$u$的子节点，$w$为这条边的权值。在$u$每个子节点上有许多“物品”，“物品”总数即为以$v$为根的子树上用户的个数；每个“物品”所具有的价值即为其最大利润，即$f[v][j]$。同时不应忽略边权对利润带来的影响。

注意细节处理及边界。代码如下：

题目链接

给定数轴上$n$个点，给出$m$条独立的指令，将编号为$[l,r]$ 的点集中到$[k,k+r-l]$的位置且这些点个点位置不能重合，求每次命令中移动的点的距离和的最小值
（$n,m≤5×10^5, 1≤a_i,K≤10^6$）

感谢@oy的贡献

题目链接

给定一个长度为$n$的数组$a$，取$k$个各不相同的连续区间$[l,r]$ 使得这些区间所有元素的异或和的和最大，求这个最大值
（$ 1 \le n \le 5 \times 10^5,1\le k \le min(\frac{n(n-1)}{2},2\times 10^5),0\le a_i \le 4294967295$）

感谢@oy的贡献