HNOI2018省选集训 Day1
Tree
直接大力讨论+树剖
当前根为rt，u和v的lca是lca(u,v),lca(u,rt),lca(v,rt)中深度最大的一个（以1为根）
子树区间也讨论一下
function
转换题意，变成有1e9*n的矩阵，每列权值相同，每次可以向上/左上走一格，最小化以某个点为起点的经过权值和。
首先方案一定是先往左上走若干步，走到权值较小的一列直接走到顶
那么走到第i列往上的答案是关于(x-y)（起点的x,y）的一次函数。考虑按y顺序加入直线，最小值即为一割上凸壳。然后有性质保证斜率单增，直接单调栈。统计答案在凸包上二分出当前(x-y)的位置即可。注意每列的一次函数有定义域。
or
首先有朴素dp：
[d p[i][j]=sum_{k=1}^{j} d p[i-1][j-k] imes 2^{j-k} imesleft(egin{array}{l}j \kend{array}
ight)
]
直接ntt优化是(nklog)的
考虑计算(f_i=sum_{j=0}^kdp[i][j])，展开组合数得到
[egin{align}frac{d p[i][j]}{j !}&=sum_{k=1}^{j} frac{d p[i-1][j-k] imes 2^{j-k}}{(j-k) !} imes frac{1}{k !}\F_{i}(x)&=F_{i-1}(2 x) imesleft(e^{x}-1
ight) \F_{n}(x)&=prod_{i=0}^{n-1} e^{2^i x}-1end{align}
]
这个可以直接倍增
[F_{n}(x)=F_{n/2}(x) imes F_{n/2}left(2^{frac{n}{2}} x
ight)
]
for else
另外这三道题在BZOJ上是5379~5381