3789: 连通块(第二轮03)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：4
解决：2
题目描述
给定一棵根为1的，包含n个点的树。其中第i个点的权值为ai， dfs序为 dfni 。
现在你需要在这棵树上找到一个连通块，连通块需要满足题目给定的 m个限制，每个限制 用两个正整数 u, v描述。要么 u, v2T 不同时存在于这个连通块中，要么 u, v在这个连通块 上的 dfs 序相邻。请在这棵树上找到满足题目限制条件的权值之和最大的连通块。
备注 1：
一个结点可能有多个孩子结点，这些孩子是有dfs的先后顺序的，df 顺序就是题目输入的顺序。
备注 2：
连通块的 dfs 序的定义： 找到连通块在原树上深度最小的点开始 dfs，然后仍然根据题目 读入的顺序获取每个点的 dfs 顺序。
大的来了（指样例）sample.zip
输入
第一行包含两个正整数 n, m，表示结点的个数和限制的个数；
第二行包含 n 个整数，第 i 个整数为第 i 个结点的权值 vali (−10^9 ≤ vali ≤ 10^9)
接下来的 n 行里， 第 i 行的第一个数字为一个非负整数 si，表示第 i 个结点的孩子个数， 然后给出 s_i 个正整数按顺序表示它的所有孩子编号。
接下来的 m 行，每行给出两个正整数 u, v (1 ≤ u, v ≤ n) 描述一个约束，表示最终的连 通块中 u, v 的 dfs 序不能相邻。
输出
输出一行一个整数表示答案。
样例输入 复制
6 3
2 2 1 3 2 5
2 2 6
3 3 4 5
0
0
0
0
3 4
5 6
2 6样例输出 复制
12提示
【备注】
测试点编号 n ≤ m ≤ 特殊性质
1 − 4 20 3 保证树随机
5 − 8 100000 5 保证树随机
9 − 12 100000 20 保证树随机，对于所有限制，保证u是v在树上的第一个儿子
13 − 14 100000 20 保证树随机
15 − 16 100000 12
17 − 20 100000 21
测试点编号 n ≤ m ≤ 特殊性质
1 − 4 20 3 保证树随机
5 − 8 100000 5 保证树随机
9 − 12 100000 20 保证树随机，对于所有限制，保证u是v在树上的第一个儿子
13 − 14 100000 20 保证树随机
15 − 16 100000 12
17 − 20 100000 21