题目描述

塔子哥是一名远近闻名的魔法师。

这天他受邀来到了一个国家，来帮这个国家的国王解决一个问题。这个国家的国王年轻时曾有一颗非常美丽的树，但是国王却不小心惹怒了一个十分邪恶的黑魔法师，于是黑魔法师施法，让这棵树变得十分丑陋。现在，这棵树一共有$n$个节点，根节点为$1$号节点，其深度为$1$。每个节点都被黑魔法师随机施加了一个丑陋值，丑陋值越大，越影响这棵树的美观度，影响值为该节点的深度乘其丑陋值。

思路：dp

给定一棵树，树上每个节点的丑陋值为节点深度乘节点丑陋值$a_i$，树的丑陋值为所有节点丑陋值的和。我们能够将一整棵子树裁剪下来，并给某一个节点当子树，求最小的树的丑陋值。

树的深度能够通过一次遍历得到结果，因此树的每个节点的丑陋值也能够在计算节点的深度时，通过递归计算出来。

为了让整棵树的丑陋值最小，一个很直观的想法就是，将裁剪出来的这棵子树嫁接到根节点，也就是1号节点下。

定义：$sum[i]$表示节点$i$及其子树的丑陋值的和(不乘深度)，$depth[i]$表示第$i$个节点的深度。