#P18063. Magical Puzzles
Magical Puzzles
Magical Puzzles
给定一棵有 个顶点、 条边的树。第 条边的权值为 。令 表示顶点 之间唯一路径上所有边权的和,其中 。
树上有 个谜题。第 个谜题需要 条信息,这些信息分别位于指定的边上。多条信息可以位于同一条边上。
从顶点 沿唯一路径前往顶点 时,你会获得沿途每条边上的所有信息。如果对每个谜题,你要么没有获得它的任何信息,要么获得了它的全部信息,就称这次旅程成功。没有任何信息的谜题不会限制旅程。
求所有无序端点对对应的成功旅程的距离和,即
$$\sum_{\substack{1\le S\le T\le N\\(S,T)\text{ 的旅程成功}}}d(S,T),$$答案对 取模。
输入格式
第一行两个整数 。
接下来 行,第 行三个整数 ,表示编号为 的边连接 ,权值为 。
接下来 行,第 行先给出整数 ,再给出 个整数 ,表示该谜题各条信息所在的边的编号。这些编号允许重复。
输出格式
输出一个整数,表示答案对 取模的结果。
数据范围
,,,。
令 ,保证 ,,。
样例
5 4
1 2 3
1 4 1
1 5 6
4 3 2
2 4 4
1 1
0
2 3 4
17