[hihocoder1063]Travel on a Tree
这两天打比赛打的贼烂，我还是菜啊。这里记一个比赛原题，一个树型DP。
这两天打比赛打的贼烂，我还是菜啊。这里记一个比赛原题，一个树型DP。
难度：省选/NOI-
策策同学特别喜欢逛公园。公园可以看成一张$N$个点$M$条边构成的有向图，且没有自环和重边。其中1号点是公园的入口，$N$号点是公园的出口，每条边有一个非负权值， 代表策策经过这条边所要花的时间。
策策每天都会去逛公园，他总是从1号点进去，从$N$号点出来。
策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个 特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果1号点到$N$号点的最短路长为$d$，那么策策只会喜欢长度不超过$d + K$的路线。
策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗？
为避免输出过大，答案对$P$取模。
如果有无穷多条合法的路线，请输出-1。
对于$100\%$的数据, $1 \le P \le 10^9,1 \le a_i,b_i \le N ,0 \le c_i \le 1000,k\leq 50$。
难度：省选/NOI-
最近lxhgww 又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。
通过一段时间的观察，lxhgww 预测到了未来$T$天内某只股票的走势，第$i$天的股票买入价为每股$AP_i$，第$i$天的股票卖出价为每股$BP_i$（数据保证对于每个$i$，都有 $AP_i \geq BP_i$），但是每天不能无限制地交易，于是股票交易所规定第$i$天的一次买入至多只能购买$AS_i$股，一次卖出至多只能卖出$BS_i$股。
另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔$W$天，也就是说如果在第$i$天发生了交易，那么从第$i+1$天到第$i+W$天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的股票数不能超过$MaxP$。
在第1天之前，lxhgww 手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然$T$天以后，lxhgww 想要赚到最多的钱，聪明的程序员们，你们能帮助他吗？
难度：省选/NOI-
T国有N个城市，用若干双向道路连接。一对城市之间至多存在一条道路。
在一次洪水之后，一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况，但直到现在几乎没有消息传回。
幸运的是，此前T国政府调查过每条道路的强度，现在他们希望只利用这些信息估计灾情。具体地，给定每条道路在洪水后仍能通行的概率，请计算仍能通行的道路恰有N-1条，且能联通所有城市的概率。
难度：省选/NOI-
最近在生物实验室工作的小T遇到了大麻烦。由于实验室最近升级的缘故，他的分格实验皿是一个长方体,其尺寸为$abc$，$a、b、c$均为正整数。为了实验的方便，它被划分为$abc$个单位立方体区域，每个单位立方体尺寸为$1$。用$(i,j,k)$标识一个单位立方体，$1<=i<=a，1<=j<=b，1<=k<=c$。这个实验皿已经很久没有人用了，现在，小T被导师要求将其中一些单位立方体区域进行消毒操作（每个区域可以被重复消毒）。
而由于严格的实验要求，他被要求使用一种特定的F试剂来进行消毒。 这种F试剂特别奇怪，每次对尺寸为$xyz$的长方体区域（它由$xyz$个单位立方体组 成）进行消毒时，只需要使用$min\{x,y,z\}$单位的F试剂。F试剂的价格不菲，这可难倒了小T。
现在请你告诉他，最少要用多少单位的F试剂。(注：$min\{x,y,z\}$表示x、y、z中的最小者。)
本文是快速傅里叶变换（FFT）的后续。这一篇文章和ACM确实没有什么关系，它是对FFT在工程领域应用的一个介绍。
从上一篇文章中，我们认识了FFT在ACM中的一个应用：求卷积。但事实上，FFT在信号处理领域有着重要的应用，它在一些信号处理领域（比如音频解析）方面如何应用？与ACM中FFT有哪些区别与联系？这是本文讨论的问题。
值得注意的是，本文并不是在一个专业的角度去阐述，而是在一个尽可能通俗易懂的角度来探讨FFT。下面我们用一个实例：解析一段wav中声音的频率信息。
有必要整理一下网络流模型了，本文长期更新。以下题目许多出自网络流24题专题，点击标题可跳转。前缀知识：网络流。
介绍虚树，一个解决树上动态规划的利器。
难度：省选/NOI-
现在我们的手头有$N$个软件，对于一个软件$i$，它要占用$W_i$的磁盘空间，它的价值为$V_i$。我们希望从中选择一些软件安装到一台磁盘容量为$M$计算机上，使得这些软件的价值尽可能大（即$V_i$的和最大）。
但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件$j$（包括软件$j$的直接或间接依赖）的情况下才能正确工作（软件$i$依赖软件$j$)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。
我们现在知道了软件之间的依赖关系：软件i依赖软件$D_i$。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则$D_i=0$，这时只要这个软件安装了，它就能正常工作。
继四边形不等式和单调队列之后的另一个DP优化方法，这样常见的DP优化方法基本全了。