删除题目

【题目描述】

敌方的通信网络构成一个 $n$ 个节点的树，其中任意两个不同的节点间存在联络，即总共存在 $\frac{n(n-1)}{2}$ 对联络。节点 $1$ 为根。

你可以在一些边上放置炸弹来截断敌方的通信。具体的，如果在一条边上放置炸弹，那么所有需要经过该边的联络都会被截断，而你也需要积累一定的的疲惫值。

现在你可以从任意节点出发并走到任意节点，并在简单路径上放置任意多个炸弹。最后，你的收益是 $P - W$，其中 $P$ 为你截断的联络总数，$W$ 为你积累的疲惫值之和。

你希望最大化收益，请求出收益的最大可能值。

【输入格式】

第一行包含一个整数 $n$。

接下来 $n-1$ 行，第 $i$ 行两个整数 $p,w$，表示节点 $i$ 的父亲为 $p$，且在它与父亲之间的边上面放置炸弹的疲惫值为 $w$。

【输出格式】

一个整数，表示你的最大可能收益。

【样例输入1】

5
1 6
1 1
3 1
4 9

【样例输出1】

6

【样例说明】

从节点 $1$ 出发走到节点 $4$，并在 $(1,3),(3,4)$ 两条边上放置炸弹，此时 $P=8,W=2$。 

若从节点 $1$ 出发走到节点 $5$，并在 $(1,3),(4,5)$ 两条边上放置炸弹，此时 $P=8,W=10$。

【样例输入2】

10
1 0
1 2
3 -1
4 1
4 4
6 6
4 3
3 4
8 9

【样例输出2】

33

【样例下载】

样例下载

【数据规模与约定】

对于前 $10\%$ 的数据，保证 $1 \le n \le 10$。 

对于前 $30\%$ 的数据，保证 $1 \le n \le 1000$。 

另有 $20\%$ 的数据，保证树是一条链。 

对于 $100\%$ 的数据，保证 $1 \le n \le 10^5, |w| \le 10^8$。

【来源】

蒙德城算法竞赛 T4