题目描述

给出一棵含 $n$ 个洞（蚂蚁的安身之地）的树。在这颗树上，共有 $m$ 只蚂蚁。一开始第 $i$ 只蚂蚁在洞 $s_i$ 里，它想沿着树上的最短路以速度 $v_{i}$ 爬到洞 $t_i$ 里。到达目的地后，就钻入洞里。在旅途中，若两只蚂蚁到达同一位置（相遇或追及），为了交换信息，它们就会碰触角。钻入洞里的蚂蚁，就不会再和其他蚂蚁碰触角。即只有旅途中的蚂蚁才会碰触角。注意在起点或目的地的瞬间都算在旅途中。保证没有两只蚂器速度一样，求总共碰触角的次数。

输入格式

本题有多组数据，第一行包含一个正整数 $t(1 \le t \le 20)$，表示数据组数，下面共描述了t$ 组数据。

对于每组数据。 第一行包含一个整数 $n(1 \le n \le 10^ {5} )$。接下来 $n-1$ 行，每行包含三个正整数 $( u_ {i} , v_ {i} , w_ {i} )(1 \le u_ {i} , v_ {i} \le n, u_ {i} \neq v_ {i} ,1 \le w_ {i} \le 10^ {3} )$，表示洞 $u_ {i}$ 和洞 $v_ {i}$ 相邻，且相距 $w_i$ 单位长度。

再接下来一行包含一个整数 $m(1 \le m \le 1000)$。再接下来 $m$ 行，每行包含三个正整数 $(s_i, t_i, v_i)(1<s_i,t_i\le n,1 \le v_i \le 10^{6} )$，表示第 $i$ 只蚂蚁从洞 $s_i$ 以速度 $v_i$ 爬到洞 $t_i$。

输出格式

对于每组数据，打印一行包含一个整数，表示总共碰触角的次数。

1
3
1 2 1
2 3 1
3
1 3 2
3 1 1
1 2 3

2

题目来源

Play with tree By Amber