P14658 积云四月

给定一棵 $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$ 值。

- 子任务一 $(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$