HDU - 5886 给定一棵树，每条边都有一个权值 定义一条边的战术价值为割去这条边后 剩下的图中最长链的长度 求随机割掉一条边，战术价值的期望 题目要求乘以 N−1 N-1，所以直接把概率消掉了 所以只要求割去每条边后的最长链长度即可 这就转化为了一个树形dp 首先割去一条边 u−>v u->v 后，最长链可能在 v v 为根的子树中 这个简单地做一次树形dp