题目描述

给定一棵 $n$ 个结点的树，树上第 $i$ 条边连接了结点 $u_i,v_i$，长度是 $l_i$。

本题的树与一般的树有所不同，它是连续的，意思是每条边实际上可以看成是无穷个连续点的集合，这里我们认为这条边的两个端点也属于这个集合。

进一步的，我们可以用 $Set(u,v)$ 表示从结点 $u$ 到结点 $v$ 的唯一简单路径上包含的所有边上的集合的并，特别的当 $u=v$ 时 $Set(u,v)$ 就仅包含了 $u$ 这一个点。

给出树上的 $m$ 个点集合 $S_1,S_2\dots S_m$，你要从每个 $S_i$ 里选出一个点 $x_i$，注意这里的 $x_i$ 可能在某条边上。

每个 $S_i$ 由如下方式给出：

• 给出 $k_i$ 个结点 $p_{i,1},p_{i,2}\dots p_{i,k_i}$，那么 $S_i=\cup_{1\leq u,v\leq k_i}Set(p_{i,u},p_{i,v})$。

我们称一个整数 $z$ 合法，当且仅存在一种选择 $x_1,x_2\dots x_m$ 的方式，使得 ：

$$D(x_1,x_2)+D(x_2,x_3)+\dots D(x_{m-1},x_m)=z$$

这里的 $D(x,y)$ 定义为两个点在树上的距离。

请你求出有多少种不同的合法的 $z$ 值？

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行三个整数 $u_i,v_i,l_i$ 描述了树上的一条边。

接下来一行一个整数 $m$。

接下来 $m$ 行，每行先输入一个正整数 $k_i$ ，接下来 $k_i$ 个正整数表示 $p_{i,1},p_{i,2}\dots p_{i,k_i}$。

输出格式

一行一个整数有多少种不同的合法的 $z$ 值。

7
2 4 2
7 4 2
4 5 3
3 5 1
4 6 3
6 1 1
3
2 2 1 
1 5 
4 6 6 4 1 

9

提示

• 子任务一 $(5\%)$，$n,\sum k_i\leq 300$。
• 子任务二 $(10\%)$，$n,\sum k_i\leq 5000$。
• 子任务三 $(10\%)$，$\sum k_i\leq 5000$。
• 子任务四 $(15\%)$，树是一条链。
• 子任务五 $(15\%)$，$k_1=1$。
• 子任务六 $(15\%)$，$k_i=2$。
• 子任务七 $(15\%)$，$n,\sum k_i\leq 10^5$。
• 子任务八 $(15\%)$，无特殊限制。

对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^5,\sum k_i\leq 5\times 10^5,1\leq m\leq 5\times 10^5,k_i\geq 1,1\leq l_i\leq 10^9$