动态规划：可以认为由状态，转移两个过程构成
树上优化技巧
P1272 重建道路
设,dp[i][j]为包含i的大小为j的连通块的最小操作次数，枚举i的每个子树一个个合并上去。
考虑两个点i,j只会在lca处有计算时间贡献，所以是\(O(n^2)\)的
LOJ160. 树形背包
先跑dfs序，设dp[i][w]为从第i个位置开始的后缀，容量为w的最大价值。
设第i个位置为x,则\(dp[i+1][w-w[x]]\)可以转移过来。
或者直接跳过\(x\)所在的子树，从\(dp[low[x]+1][w]\)转移过来。
多项式优化（拉插）
首先可以高斯消元，\(O(n^3)\)
然后考虑其实可以构造，详见拉格朗日插值法
自然数幂和
拉插经典应用
\(F(k)=\sum_{i=1}^{n}i^k\)，求\(F(k)\)
\(k<=2000,n<=10^9\)
令\(f(x)=x^k\)
考虑计算\(f(x)-f(x-1)=x^k-(x-1)^{k}\)
将\((x-1)^k\)二项式展开，发现\(f(x)-f(x-1)\)的\(k\)次项正好没了，所以\(f(x)-f(x-1)\)是\(k-1\)次的。
对\(f(x)-f(x-1)\)求和，我们知道对一个\(y\)次的多项式\(g(x)\)求\(\sum_{i}g(i)\)是\(y+1\)次的。
所以\(\sum_{i=1}^{x}(f(x)-f(x-1))\)是\(k\)次的，即\(f(x)\)是\(k\)次的。
再做一次,所以\(F(x)=\sum_{i=1}^{x}f(x)\)是\(k+1\)次的。
然后拉插。
CF1967C Fenwick Tree
考虑枚举区间结尾x，取出长度为\(lowbit(x)\)的一段，区间内每个点到终点的贡献系数的多项式（自变量为k）是\(log(n)\)级的，因为贡献路径长度为\(log(n)\)量级。
所以最后每个位置必定是一个对k的O(log) 阶多项式，所以直接暴力跑前 log 次，然后对每个位置都插一遍就做完了。
P8290 [省选联考 2022] 填树
极差小于等于\(K\)不好做，考虑枚举最小值权值\(x\)，那么所有路径上的点的权值都要在\([x,x+k]\)内，现在每个路径上的点\(i\)的权值范围是\([max(x,l_i),min(x+k,r_i)]\)。
先思考如何暴力，我们显然只关心每个点权值范围的大小，也就是\(max(0,min(x+k,r_i)-max(x,l_i)+1)\)。
于是可以直接枚举路径，把路径上所有范围大小乘起来即可。
但是发现有一个问题，这样做不能保证最小权值为\(x\)，可以计算所有路径上的点权值在\([x+1,x+k]\)内的答案，简单容斥掉。
考虑优化，计算范围的时候有\(min\)和\(max\)，这样十分的不好计算，对每个点分类讨论一下。
P10013 [集训队互测 2023] Tree Topological Order Counting
首先考虑计算一个子树的合法拓扑序数量。
假设一个点x有两个儿子a和b，dp[i]为i子树内拓扑序的数量。
不难发现有\(dp[x]=dp[a]\times dp[b] \times C(sz(a)+sz(b),sz(a))\)，可以理解为siz(x)个位置内随便选取siz(a)个位置把一个a的拓扑序顺序放进去，剩下的位置把一个b的拓扑序顺序放进去。
如果x有很多个儿子也是一样的，手推一下不难得出，比如有一个儿子c，就乘上\(dp[c] \times C(sz(a)+sz(b)+sz(c),sz(a)+sz(b))\)$。
把组合数拆一下，最终的方案数就是sz总和的阶乘除以每个sz各自的阶乘。
sz总和显然是\(sz(x)-1\)，即分子为\((sz(x)-1)!\),发现x在计算其父亲的答案的时候会贡献一个\(\frac{1}{sz(x)!}\)。
所以以x为根的拓扑序数量为\(\frac{sz(x)!}{\prod_{y}sz(y)!}\)，其中y是x的儿子。
设f[x][i]表示x的子树内的拓扑序，表示s在x子树的拓扑序的第i位的方案数，其中s是题目中枚举的u，然后把s到根的一条链上的点跑树形dp。
不难得出，f[s][1]=dp[s]。
考虑怎么把一个点y的信息转移到父亲x,我们可以先计算除了y的x的所有的儿子的拓扑序方案数，，根据前面的结论，只需要预处理x个每个节点z的\(\frac{1}{sz(y)}\)然后把y的siz(y)的拓扑序和这个长度为\(sz(x)-sz(y)-1\)的拓扑序合并。
如果现在s在y的拓扑序中的位置为i，枚举长度为\(sz(x)-sz(y)-1\)的拓扑序中有j个在s之前，方案数为\(C(i+j-1,i-1)\times C((siz(x)-1)-i-j,sz(y)-i)\)
别忘了x一定要放在其子树拓扑序的第一位，所以\(f[i][j]\)一定要变成\(f[i][j+1]\)
根据一开始重建道路这道题的分析，单次是\(O(n^2)\)的，总时间复杂度为\(O(n^3)\)
对于点s，答案为\(\sum{i=1}^(n)f[1][i]\times b[i]\)
考虑将整个过程从上往下推，假设已知\(f[x][i]\)，怎么向下计算。
可以把\(f[i][j]\)的值该为s在\(x\)子树内的第i个位置，向上的贡献是多少
最小斯坦纳树
模板：P6192 【模板】最小斯坦纳树
首先分析为什么形成一棵树是最优的,显然如果出现环删掉任意一条边都会更优，所以选出来的是一棵树。
从小往大枚举一个关键点集S
标签：sz,拓扑,sum,计数,枚举,权值,最优化,dp From： https://www.cnblogs.com/wangwenhan/p/18383609