# 「DTOI-5」校门外的枯树## 题目背景某天放学你走出了校门发现校门外又双叒叕出现了一排树。只不过因为正值寒冬时节树的叶子都掉光了树们在寒风中瑟瑟发抖让人担心它们会不会在某一时刻失去平衡然后倒下来。## 题目描述给你校门外的一排 $T$ 棵无向有根树每棵树的根节点编号均为 $1$每棵树的每条边有其重量 $m_i$现在请你算出每棵树的不平衡度 或 该树的每个节点的子树的不平衡度好让校方帮忙加固
其实就是一道区间DP，这里不再赘述。 关于树的不平衡度，可以先对于一个节点 $u$，计算以其为根的子树中每个节点为分割点时的不平衡度。最后再将所有节点的结果合并即可。 时间复杂度为 $O(Tn)$。
关于本题的数据，最大的一组数据大小为 $3.3,\texttt{MB}$，可以通过本地编译器的内存限制。
代码：
原文地址: https://www.cveoy.top/t/topic/dRt5 著作权归作者所有。请勿转载和采集!