← 返回题目列表

Codeforces · 1023/G

G. 双鱼座

中文机器翻译题面 查看原题

一组研究人员正在研究湖泊和河流自然系统中的鱼类种群。该系统包含 $$$n$$$ 个湖泊,由 $$$n - 1$$$ 河流连接。 Each river has integer length (in kilometers) and can be traversed in both directions.通过穿越河流(即湖泊和河流的网络形成一棵树),可以在任意一对湖泊之间旅行。

There is an unknown number of indistinguishable fish living in the lakes.在 $$$1$$$ 天,鱼可以出现在任意湖泊中。鱼可以通过在河流中游泳来在湖泊之间移动。 Each fish can swim a river $$$l$$$ kilometers long in any direction in $$$l$$$ days. Further, each fish can stay any number of days in any particular lake it visits. No fish ever appear or disappear from the lake system. Each lake can accomodate any number of fish at any time.

The researchers made several observations.这些观察中的第 $$$j$$$ 是“在 $$$d_j$$$ 那天,$$$p_j$$$ 湖中至少有 $$$f_j$$$ 不同的鱼”。帮助研究人员确定生活在湖泊系统中且与观察结果不矛盾的尽可能少的鱼类总数。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 系统中湖泊的数量。

接下来的 $$$n - 1$$$ 行描述河流。 The $$$i$$$-th of these lines contains three integers $$$u_i$$$, $$$v_i$$$, $$$l_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$, $$$1 \leq l_i \leq 10^3$$$) —由第 $$$i$$$ 条河流连接的基于 $$$1$$$ 的湖泊指数以及该河流的长度。

The next line contains a single integer $$$k$$$ ($$$1 \leq k \leq 10^5$$$) — the number of observations.

接下来的 $$$k$$$ 行描述了观察结果。 The $$$j$$$-th of these lines contains three integers $$$d_j$$$, $$$f_j$$$, $$$p_j$$$ ($$$1 \leq d_j \leq 10^8$$$, $$$1 \leq f_j \leq 10^4$$$, $$$1 \leq p_j \leq n$$$) — the day, the number鱼的数量,以及第 $$$j$$$ 次观测的湖泊指数。同一天,同一个湖不会同时发生两次观测。

输出

打印一个整数——与观察结果不矛盾的最小鱼总数。

示例

输入 #1

4
1 2 1
1 3 1
1 4 1
5
1 1 2
1 1 3
2 2 1
3 1 4
3 1 2

输出 #1

2

输入 #2

5
1 2 1
1 3 1
1 4 1
1 5 1
4
1 1 2
2 1 3
3 1 4
4 1 5

输出 #2

2

输入 #3

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

输出 #3

10

注意

In the first example, there could be one fish swimming through lakes $$$2$$$, $$$1$$$, and $$$4$$$, and the second fish swimming through lakes $$$3$$$, $$$1$$$, and $$$2$$$.

In the second example a single fish can not possibly be part of all observations simultaneously, but two fish swimming $$$2 \to 1 \to 4$$$ and $$$3 \to 1 \to 5$$$ can.

在第三个示例中,一条鱼可以从 $$$1$$$ 湖移动到 $$$5$$$ 湖,其他鱼则始终留在湖中:$$$4$$$ 湖中两条鱼,$$$5$$$ 湖中六条鱼,$$$3$$$ 湖中一条鱼。湖泊系统如图所示。