签到题
题面
给你一个 (n) 个点的无根树，每个点有点权 (a_x) ，构造一个 dfs 序 (b) ，使得 (sumlimits a[x]*b[x]) 最小，(b[x]) 指的是第几个遍历的点是 (x)。
(nle 10^5) , (a_x le 10^9) 。
题解
这很不签到 ({color{White}{cjz:这水题本神仙1秒切10道}})
分析
算法:显然树形dp。 ({color{White}{可不是嘛,这题在树形DP专题里}})
用脚思考: O((n^2))过不去。
用手思考:应该是先把一棵子树搜完,再回溯,否则答案肯定不优。
设状态
设 f[x][L][R] 表示将 (x) 的子树从数字 (L) 连续标号到 (R) 花费的最小值。
这必 TLE/MLE 啊，空间都撑不住了。
能发现当 L 不变时，R 是确定的所以二维数组就够了。
设 f[x][L] 表示将 (x) 的子树从数字 (L) 连续标号到 (L+size_x-1) 花费的最小值。
这必 TLE/MLE 啊，空间照样撑不住。
设 f[x] 表示将 (x) 的子树从 (1) 开始标号花费的最小值，即 (sumlimits_{y in x的子树} a[y]*b[y]) , (b) 是一个 (1) 开头的排列
这必不 TLE/MLE 啊，空间不大，时间可能不大。
转移
状态的定义使得咱们在转移时要将 (f[x]) 加一个偏移量(说白了就是 (b) 整体加一个值)。
假如 (f[y_1]),(f[y_2]) 要合并到 (f[x]) 上面。
设 (sum[x]=sumlimits_{y in x的子树}a[y]) ，就是子树的权值和。
那么有 (f[x]=min(f[y_1]+f[y_2]+sum[y_2]*size[x_1],f[y_1]+f[y_2]+sum[y_1]*size[x_2]))。
这比的就是先遍历 (y_1) ，还是 (y_2) 更优秀。
那么问题来了？
子节点多的话 O((p!)) 必 TLE 啊，所以我放弃了这道题。
用头思考:可以按照 (frac{sum}{size}) 从大到小排序，为什么自己想。
欸嘿!
这样就能 O((n)) 求出以 (root) 为根的答案了。
强烈建议先写一下这份代码。
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 我是分割线 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
你刚刚是不是说了以 root 为根？
是的，所以那分代码还是会 TLE。
啊这，我又放弃了这道题。
欸，等等好像有一个叫做 ({color{Violet}{换根DP}}) 的圣物。
用脑思考:这个换根好像很难。 ({color{White}{cjz:不，你就没脑子}})
假设我们有了 (f[x]) ，思考怎么向 (f[y]) 转移。({color{White}{cjz:像癌症一样转移}})
原先求 (f[3]) 时我们用的是 (f[4]),(f[5])，当我们把根从 1 转移到 3 是只不过是多了一个 (f[1]) 。
那着就好办了，转移时我们设父亲这一坨 (f[fa]) 是 ff ，他的子树大小是 _size ，他子树的权值和是 Sum 。
有：
LL sUm=a[x];//前面的权值和
_sIze=1;//前面的子树大小
for(int i=0,End=g[x].size();i<End;i++){//g[x] 是按照 sum/size 降序的。
if(g[x][i].ver!=F)//不能像 1 -> 2 ->1 ->2 ->1 这样打太极拳(云手这一式)
dp(g[x][i].ver,//转移后的根
x,//转移后的根的父亲
n-siz_e[g[x][i].ver],//父亲的大小很显然，n-儿子的大小
allsum-sum[g[x][i].ver],//父亲的权值和很显然，权值总和-儿子的权值和
f[x]-f[g[x][i].ver]-g[x][i].sum*_sIze-g[x][i].size*(allsum-sUm-g[x][i].sum)
//这个 ff 有点恶心，大体就是f[x]减去f[y]的贡献，但这造成了原来排在y后面的y2的标号变化
//需要抵消这个变化，后面所有点权和=点权总和-排在y前面的点权和(包括y)
);
sUm+=g[x][i].sum;
_sIze+=g[x][i].size;
}