PT07I - The Ants in a Tree

no tags 

In Amber's childhood, he usually liked to observe some little things for tickling his little curiosity. He often found it interesting to climb up a tree, sit on a branch and watch the movement of a group of lovely ants on the branches of the tree.

Amber finds there are n ant holes and m ants in the tree now. Because of his careful observation, he knows all ants' behaviors, the i-th ant wanna travel from one hole si to another hole ti at the speed vi.

During the ant's travel, if two ants arrive at the same position (meet or chase), they will touch their feelers for exchanging the information about food or danger. Even at the moment that the travel starts or finishes, the ant can also touch other's feelers. But after the travel finishes, the ant will enter into the hole and never touch feelers. What amber wonders is to count the times of touchings during the whole traveling process.

Consider there are n - 1 branches in the tree. Each branch connects the adjacent ant holes and has a particular length. Assume there is always a path that consists of branches between any two ant holes. Assume that no two ants have the same speeds and the touching doesn't cost any time.


Input consists of multiple testcases. The first line contains one integer t (1 <= t <= 20). For each testcase, the input format is following.

The first line contains one integer n (1 <= n <= 106). In next n - 1 line, the i-th line contains an integer triple (ui, vi, wi) (1 <= ui, vi <= n, ui != vi, 1 <= wi <= 103). The triple means there is a branch with the length wi between node ui and node vi.

The next line contains one integer m (1 <= m <= 103). In next m line, the i-th line contains an integer triple (si, ti, vi) (1 <= si, ti <= n, 1 <= vi <= 106). The triple means that the i-th ant's travel is from si to ti at the speed vi.


For each testcase, print a line that consists of an integer that means the times of the feeler touchings.


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


Note: It's a partly correct problem, so score is set for each case. When you pass all cases, you'll get 300 points

Added by:Thanh-Vy Hua
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:Co-author Amber