题目描述

给出一棵含 $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 \ne 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 \le 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