【题目大意】
有$n-1$个城市和$n$个乡村，它们构成一个二叉树。恰有一条公路和一条铁路通向每个城市，没有道路通向乡村，首都是编号为1的城市。每个乡村有三个参数$a,b,c$，每个乡村的不方便值为$c*(a+x)*(b+y)$，其中$x,y$分别代表这个乡村到首都要经过$x$条未修缮的公路和$y$条未修缮的铁路。对于每个城市，从通向它的两条路中选择一条修缮，求每个乡村的不方便值的最小总和。
【思路分析】
树形DP安排上
$f[x][i][j]$表示从$x$号节点到首都要经过$i$条未修缮的公路和$j$条未修缮的铁路，其子树中的所有乡村节点的不方便值之和。
如果$x$是乡村节点，那么直接枚举$i,j$求$f[x][i][j]=c[x]*(a[x]+i)*(b[x]+j)$
如果$x$是城市节点，那么枚举是修缮公路还是铁路，设$lson$是通过个公路到达的子节点，$rson$是通过铁路到达的子节点，转移方程为$f[x][i][j]=min(f[lson][i+1][j]+f[rson][i][j],f[lson][i][j]+f[rson][i][j+1])$
最后的答案就是$f[1][0][0]$
据说有方法可以优化一下空间？emmm有空再看叭QAQ
【代码实现】
原文：https://www.cnblogs.com/THWZF/p/11589768.html