{"raw_statement":[{"iden":"statement","content":"A group of researchers are studying fish population in a natural system of lakes and rivers. The system contains $n$ lakes connected by $n - 1$ rivers. Each river has integer length (in kilometers) and can be traversed in both directions. It is possible to travel between any pair of lakes by traversing the rivers (that is, the network of lakes and rivers form a tree).\n\nThere is an unknown number of indistinguishable fish living in the lakes. On day $1$, fish can be at arbitrary lakes. Fish can travel between lakes by swimming the rivers. 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.\n\nThe researchers made several observations. The $j$\\-th of these observations is \"on day $d_j$ there were at least $f_j$ distinct fish in the lake $p_j$\". Help the researchers in determining the smallest possible total number of fish living in the lake system that doesn't contradict the observations."},{"iden":"input","content":"The first line contains a single integer $n$ ($1 \\leq n \\leq 10^5$) — the number of lakes in the system.\n\nThe next $n - 1$ lines describe the rivers. 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$) — $1$\\-based indices of lakes connected by the $i$\\-th river, and the length of this river.\n\nThe next line contains a single integer $k$ ($1 \\leq k \\leq 10^5$) — the number of observations.\n\nThe next $k$ lines describe the observations. 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 of fish, and the lake index of the $j$\\-th observation. No two observations happen on the same day at the same lake simultaneously."},{"iden":"output","content":"Print one integer — the smallest total number of fish not contradicting the observations."},{"iden":"examples","content":"Input\n\n4\n1 2 1\n1 3 1\n1 4 1\n5\n1 1 2\n1 1 3\n2 2 1\n3 1 4\n3 1 2\n\nOutput\n\n2\n\nInput\n\n5\n1 2 1\n1 3 1\n1 4 1\n1 5 1\n4\n1 1 2\n2 1 3\n3 1 4\n4 1 5\n\nOutput\n\n2\n\nInput\n\n5\n2 5 1\n5 1 1\n2 4 1\n5 3 3\n6\n5 2 4\n2 1 1\n2 1 3\n2 2 4\n4 7 5\n4 1 2\n\nOutput\n\n10"},{"iden":"note","content":"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$.\n\nIn 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.\n\nIn the third example one fish can move from lake $1$ to lake $5$, others staying in their lakes during all time: two fish in lake $4$, six fish in lake $5$, one fish in lake $3$. The system of lakes is shown on the picture.\n\n<center>![image](https://espresso.codeforces.com/97b6a424f3777120e6c3f1d40386477f8becc41e.png)</center>"}],"translated_statement":[{"iden":"statement","content":"一组研究人员正在研究一个由湖泊和河流组成的自然系统中的鱼类种群。该系统包含 $n$ 个湖泊，由 $n - 1$ 条河流连接。每条河流具有整数长度（单位：千米），且可双向通行。任意两个湖泊之间均可通过河流相互到达（即湖泊与河流构成一棵树）。\n\n有若干条无法区分的鱼生活在这些湖泊中。在第 $1$ 天，鱼可以位于任意湖泊。鱼可以通过游泳穿越河流在湖泊间移动。每条鱼可以在任意方向上用 $l$ 天时间游过长度为 $l$ 千米的河流。此外，每条鱼可以在访问的任意湖泊中停留任意天数。鱼的数量在整个系统中始终保持不变，不会新增或消失。每个湖泊在任何时刻均可容纳任意数量的鱼。\n\n研究人员进行了若干次观测。第 $j$ 次观测为：“在第 $d_j$ 天，湖泊 $p_j$ 中至少有 $f_j$ 条不同的鱼”。请帮助研究人员确定与所有观测结果不矛盾的最小可能的鱼的总数。\n\n第一行包含一个整数 $n$（$1 lt.eq n lt.eq 10^5$）——系统中的湖泊数量。\n\n接下来 $n - 1$ 行描述河流。第 $i$ 行包含三个整数 $u_i$、$v_i$、$l_i$（$1 lt.eq u_i, v_i lt.eq n$，$u_i eq.not v_i$，$1 lt.eq l_i lt.eq 10^3$）——表示第 $i$ 条河流连接的两个湖泊的 1-索引编号及其长度。\n\n下一行包含一个整数 $k$（$1 lt.eq k lt.eq 10^5$）——观测次数。\n\n接下来 $k$ 行描述观测。第 $j$ 行包含三个整数 $d_j$、$f_j$、$p_j$（$1 lt.eq d_j lt.eq 10^8$，$1 lt.eq f_j lt.eq 10^4$，$1 lt.eq p_j lt.eq n$）——表示第 $j$ 次观测的日期、鱼的数量和湖泊编号。没有两个观测同时发生在同一湖泊的同一天。\n\n请输出一个整数——与所有观测不矛盾的最小鱼的总数。\n\n在第一个例子中，可能存在一条鱼依次经过湖泊 $2$、$1$ 和 $4$，另一条鱼依次经过湖泊 $3$、$1$ 和 $2$。\n\n在第二个例子中，单条鱼不可能同时参与所有观测，但两条鱼分别沿路径 $2 arrow.r 1 arrow.r 4$ 和 $3 arrow.r 1 arrow.r 5$ 移动是可以的。\n\n在第三个例子中，一条鱼可以从湖泊 $1$ 移动到湖泊 $5$，其余鱼在整个过程中停留在各自湖泊：湖泊 $4$ 中有两条鱼，湖泊 $5$ 中有六条鱼，湖泊 $3$ 中有一条鱼。湖泊系统如图所示。"},{"iden":"input","content":"第一行包含一个整数 $n$（$1 lt.eq n lt.eq 10^5$）——系统中的湖泊数量。接下来 $n - 1$ 行描述河流。第 $i$ 行包含三个整数 $u_i$、$v_i$、$l_i$（$1 lt.eq u_i, v_i lt.eq n$，$u_i eq.not v_i$，$1 lt.eq l_i lt.eq 10^3$）——表示第 $i$ 条河流连接的两个湖泊的 1-索引编号及其长度。下一行包含一个整数 $k$（$1 lt.eq k lt.eq 10^5$）——观测次数。接下来 $k$ 行描述观测。第 $j$ 行包含三个整数 $d_j$、$f_j$、$p_j$（$1 lt.eq d_j lt.eq 10^8$，$1 lt.eq f_j lt.eq 10^4$，$1 lt.eq p_j lt.eq n$）——表示第 $j$ 次观测的日期、鱼的数量和湖泊编号。没有两个观测同时发生在同一湖泊的同一天。"},{"iden":"output","content":"请输出一个整数——与所有观测不矛盾的最小鱼的总数。"},{"iden":"examples","content":"输入41 2 11 3 11 4 151 1 21 1 32 2 13 1 43 1 2输出2输入51 2 11 3 11 4 11 5 141 1 22 1 33 1 44 1 5输出2输入52 5 15 1 12 4 15 3 365 2 42 1 12 1 32 2 44 7 54 1 2输出10"},{"iden":"note","content":"在第一个例子中，可能存在一条鱼依次经过湖泊 $2$、$1$ 和 $4$，另一条鱼依次经过湖泊 $3$、$1$ 和 $2$。在第二个例子中，单条鱼不可能同时参与所有观测，但两条鱼分别沿路径 $2 arrow.r 1 arrow.r 4$ 和 $3 arrow.r 1 arrow.r 5$ 移动是可以的。在第三个例子中，一条鱼可以从湖泊 $1$ 移动到湖泊 $5$，其余鱼在整个过程中停留在各自湖泊：湖泊 $4$ 中有两条鱼，湖泊 $5$ 中有六条鱼，湖泊 $3$ 中有一条鱼。湖泊系统如图所示。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of lakes.  \nLet $ T = (V, E) $ be a tree with $ V = \\{1, 2, \\dots, n\\} $ (lakes) and $ E $ the set of $ n-1 $ edges (rivers).  \nEach edge $ e = (u, v, l) \\in E $ has a positive integer weight $ l \\in \\mathbb{Z}^+ $ representing the river length.  \nLet $ d(u, v) $ denote the shortest path distance (sum of edge weights) between lakes $ u $ and $ v $ in $ T $.  \n\nLet $ k \\in \\mathbb{Z}^+ $ be the number of observations.  \nEach observation $ j \\in \\{1, \\dots, k\\} $ is a triple $ (d_j, f_j, p_j) $, where:  \n- $ d_j \\in \\mathbb{Z}^+ $ is the day of observation,  \n- $ f_j \\in \\mathbb{Z}^+ $ is the minimum number of distinct fish observed in lake $ p_j $ on day $ d_j $,  \n- $ p_j \\in V $ is the lake index.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 10^5 $  \n2. $ 1 \\le l_i \\le 10^3 $ for all rivers  \n3. $ 1 \\le k \\le 10^5 $  \n4. $ 1 \\le d_j \\le 10^8 $, $ 1 \\le f_j \\le 10^4 $, $ 1 \\le p_j \\le n $ for all observations  \n5. All $ (d_j, p_j) $ pairs are distinct.  \n\n**Objective**  \nFind the minimum total number of fish $ F \\in \\mathbb{Z}^+ $ such that there exists a set $ \\mathcal{F} $ of $ F $ fish paths satisfying:  \n- Each fish follows a continuous walk (possibly with pauses) in the tree $ T $, moving along edges at speed 1 km/day.  \n- For each observation $ j $, at least $ f_j $ fish are present in lake $ p_j $ at time $ d_j $.  \n- Fish never enter or leave the system.  \n\nEquivalently, define for each fish a path $ \\pi: \\mathbb{R}_{\\ge 0} \\to V $, such that $ \\pi(t) $ is the lake occupied by the fish at time $ t $, with $ d(\\pi(t), \\pi(t')) \\le |t - t'| $ for all $ t, t' \\ge 0 $.  \n\nLet $ \\mathcal{O} = \\{ (d_j, p_j, f_j) \\}_{j=1}^k $.  \nMinimize $ |\\mathcal{F}| $ such that for each $ j $:  \n$$\n\\left| \\left\\{ f \\in \\mathcal{F} \\mid \\pi_f(d_j) = p_j \\right\\} \\right| \\ge f_j\n$$  \n\nThis is equivalent to covering the observation constraints with minimum number of fish paths, where a fish can satisfy multiple observations $ (d_j, p_j) $ if $ d(p_i, p_j) \\le |d_i - d_j| $.  \n\n**Reformulation as Minimum Path Cover under Temporal Distance Constraints**  \nLet $ G = (V_{\\text{obs}}, E_{\\text{feas}}) $ be a directed graph where:  \n- Each node $ v_j \\in V_{\\text{obs}} $ corresponds to observation $ j $,  \n- There is a directed edge $ v_i \\to v_j $ if a single fish can visit $ p_i $ at time $ d_i $ and $ p_j $ at time $ d_j $, i.e.,  \n  $$\n  d(p_i, p_j) \\le d_j - d_i \\quad \\text{and} \\quad d_j > d_i\n  $$  \n\nLet $ w_j = f_j $ be the demand at node $ v_j $.  \nThe problem reduces to finding the minimum number of paths in $ G $ (each path representing one fish’s itinerary) such that each node $ v_j $ is covered by at least $ w_j $ paths.  \n\nThis is the **Minimum Weighted Path Cover with Demands** problem on a DAG.  \n\n**Objective (Final Formal Statement)**  \nLet $ G = (V_{\\text{obs}}, E_{\\text{feas}}) $ be the DAG defined above, with node weights $ w_j = f_j $.  \nFind the minimum number of paths in $ G $ such that each node $ j $ is covered by at least $ w_j $ paths.  \n\nThis minimum is equal to:  \n$$\n\\max_{S \\subseteq V_{\\text{obs}}} \\left( \\sum_{j \\in S} f_j - \\sum_{\\substack{i \\to j \\in E_{\\text{feas}} \\\\ i \\in S, j \\notin S}} \\min(f_i, f_j) \\right)\n$$  \nbut more efficiently computed via **minimum flow** in a transformed network:  \n\n**Transformed Network for Minimum Flow**  \nConstruct a flow network:  \n- Source $ s $, sink $ t $.  \n- For each observation $ j $, create a node $ u_j $.  \n- Add edge $ s \\to u_j $ with capacity $ f_j $.  \n- Add edge $ u_j \\to t $ with capacity $ f_j $.  \n- For each feasible edge $ i \\to j $ in $ G $, add edge $ u_i \\to u_j $ with infinite capacity.  \n- Compute minimum $ s $-$ t $ flow such that all $ s \\to u_j $ edges are saturated.  \n\nThen, the **minimum number of fish** is equal to the value of this minimum flow.  \n\nAlternatively, by duality, it is the **maximum total demand minus maximum possible \"sharing\"** — but the cleanest formal statement is:  \n\n**Objective**  \nCompute the minimum number of fish $ F $ such that there exists a set of $ F $ walks in the tree $ T $, each walk being a time-respecting path (speed ≤ 1 km/day), satisfying all observation constraints $ \\text{fish count at } (d_j, p_j) \\ge f_j $.  \n\nThis equals the **minimum flow** in the transformed network above.  \n\nBut for direct mathematical output:  \n\n---\n\n**Objective**  \nLet $ G = (V_{\\text{obs}}, E_{\\text{feas}}) $ be a directed graph with $ V_{\\text{obs}} = \\{1, \\dots, k\\} $, and  \n$$\n(i, j) \\in E_{\\text{feas}} \\iff d_j > d_i \\text{ and } d(p_i, p_j) \\le d_j - d_i\n$$  \nLet $ w_j = f_j $.  \n\nThen the minimal number of fish is:  \n$$\n\\min \\left\\{ F \\in \\mathbb{Z}^+ \\,\\middle|\\, \\exists \\text{ a collection of } F \\text{ paths in } G \\text{ such that } \\sum_{P \\ni j} 1 \\ge w_j \\ \\forall j \\in \\{1,\\dots,k\\} \\right\\}\n$$  \n\nThis is the **minimum weighted path cover** of the DAG $ G $ with node demands $ w_j $.  \n\nEquivalently, via flow:  \nConstruct network $ \\mathcal{N} $:  \n- Nodes: $ s, t $, and $ u_j $ for each observation $ j $.  \n- Edges:  \n  - $ s \\to u_j $, capacity $ w_j $  \n  - $ u_j \\to t $, capacity $ w_j $  \n  - $ u_i \\to u_j $, capacity $ \\infty $ for each $ (i,j) \\in E_{\\text{feas}} $  \nThen:  \n$$\n\\boxed{F = \\text{min-flow}(s, t) \\text{ in } \\mathcal{N}}\n$$","simple_statement":null,"has_page_source":false}