题目描述

给出一颗有根树。树有 $n$ 个结点，被标记成 $1$ 到 $n$ 的整数，$1$ 号结点为根节点。第 $i$ 个结点的权值为 $w_i$。对于结点 $i$，有 $t_i$ 个孩子，从左到右依次为 $p_{i_1},p_{i_2},\cdots,p_{i_n}$。特别地，若 $i$ 号结点是叶结点，则 $t_i=0$。

我们对树进行深度优先搜索（DFS），每个点必须按从左到右的顺序访问每个孩子，形成一个 DFS 序列，记作 $Seq\{Seq_1,Seq_2,\ldots,Seq_n\}$。对于两个叶结点 $c$，在 DFS 序列中 $c$ 在 $a$ 和 $b$ 之间。换个方式讲，对于叶节点$a$，$b$，$c$，记 $Seq_i=a,Seq_j=b\ (i<j)$，不存在 $Seq_k=c$，使得 $i<k<j$。

每对相邻的叶节点（$a$，$b$），都存在一个影响值。影响值定义为 $a$ 到 $b$ 的路径上（不包含$a$、$b$ 的节点）的最大点权值。

定义一棵树的价值等于这棵树所有叶结点的权值之和减去每对相邻叶结点的影响值。

当然要是让你算这棵树的价值就太简单了。你的目标是对树进行一些剪枝，使树的价值最大。剪枝的方式为：如果一个结点的孩子都是叶结点，就可以将它的所有的孩子剪去。

输入格式

第一行：$n$； 第二行到第 $n+1$ 行：第 $i+1$ 行为 $w_i,t_i,p_{i_1},p_{i_2},\ldots,p_{i_n}$。

输出格式

第一行：这棵树修改后的最大价值。

样例输入

10
7 3 8 9 10
4 1 5
10 0
10 0
1 1 4
4 0
4 1 3
3 0
3 1 2
9 2 7 6

样例输出

8

数据规模与约定

对于 $100\%$ 的数据，$n \leq 10^5$，$w_i \leq 10^4$。

题目来源

版权所有者：李恺威