题目大意

给定一棵 $n$ 个节点的树，每个节点 $i$ 有两个值：

• 疲劳值 $t_i$（节点被覆盖一次就要累加一次 $t_i$）
• 高度 $h_i$

每条边 $(u,v)$ 如果 $h_u \neq h_v$，则方向已经确定（从低到高，因为挑战要求非降高度）。
如果 $h_u = h_v$，则方向未定，需要我们决定。

我们要用若干条挑战（即节点序列，相邻节点有边，且高度非降）覆盖所有边，每条边恰好属于一个挑战。
一个节点可以被多个挑战经过。
一个挑战的疲劳值是其所有节点的 $t$ 之和。
目标：最小化所有挑战的疲劳值总和。

---

转化与观察

• 一条挑战对应一条有向路径（按高度非降方向）。
• 若 $h_u \neq h_v$，边 $(u,v)$ 方向固定（$h$ 小 → $h$ 大）。
• 若 $h_u = h_v$，边方向未定。

---

第一步：若所有边方向已定

假设我们已经给每条边定向（满足 $h$ 不降方向）。

初始方案：每条边 $(u \to v)$ 作为一条长度为 $2$ 的挑战（$u \to v$）。
总疲劳值 = $\sum_{i=1}^n \deg(i) \cdot t_i$，其中 $\deg(i)$ 是 $i$ 在原树中的度数（因为每个节点出现在每条邻边上一次）。

合并挑战减少疲劳

如果存在两条挑战 $P(x,y)$ 和 $P(y,z)$，且 $y$ 在 $P(x,z)$ 上（即 $x \to y \to z$ 可拼接），可以合并成 $P(x,z)$。
合并后 $y$ 的疲劳值 $t_y$ 少算一次（原来在两个挑战中各出现一次，现在只出现一次）。
所以减少量 = $t_y$。

---

关键观察

对于节点 $i$，设：

• $in_i$ = 以 $i$ 为终点的挑战数
• $out_i$ = 以 $i$ 为起点的挑战数

初始时（每条边单独成挑战）：

• $in_i$ = 指向 $i$ 的边数
• $out_i$ = 从 $i$ 出发的边数

合并操作相当于选择某个节点 $y$，将其一个入边挑战和一个出边挑战合并，$in_y$ 和 $out_y$ 各减少 $1$，$y$ 的总疲劳减少 $t_y$。
每个节点最多可合并 $\min(in_i, out_i)$ 次（因为每次减少一对入/出）。
因此最大总减少量 = $\sum_{i=1}^n \min(in_i, out_i) \cdot t_i$。

最终最小总疲劳 = 初始总疲劳 − 最大总减少。

---

第二步：原问题（部分边方向未定）

• 对 $h_u \neq h_v$ 的边，方向固定，统计 $in'_i$ 和 $out'_i$。
• 对 $h_u = h_v$ 的边，方向未定，形成若干连通块（每个连通块内所有边 $h$ 相等）。

在这些未定向的连通块上做树形 DP。

---

DP 定义

对每个连通块任选根。设 $p_u$ 是 $u$ 的父亲。

• $f_u$：边 $(p_u, u)$ 方向为 $p_u \to u$ 时，$u$ 的子树内最大减少量。
• $g_u$：边 $(p_u, u)$ 方向为 $u \to p_u$ 时，$u$ 的子树内最大减少量。

---

转移

考虑节点 $u$，它有 $c$ 个子节点 $v_1, \dots, v_c$。

对于每个子节点 $v$：

• 如果边 $(u,v)$ 定向为 $v \to u$，则贡献 $g_v$（$v$ 的子树已算好，且 $v$ 指向 $u$）。
• 如果定向为 $u \to v$，则贡献 $f_v$。

设 $x$ = 从子节点指向 $u$ 的边数（即选择 $x$ 个 $v$ 取 $g_v$，其余取 $f_v$）。

那么 $u$ 的总减少量中，来自 $u$ 本身的贡献为：

$$\min(in'_u + x + [p_u \to u], \; out'_u + (c - x) + [u \to p_u]) \cdot t_u $$

其中 $[p_u \to u]$ 表示父亲边方向是否增加 $in_u$，$[u \to p_u]$ 同理。

我们要最大化：

$$\sum_{v \in A} g_v + \sum_{v \notin A} f_v$$

对于每个可能的 $x = |A|$。

排序优化

对子节点按 $(f_v - g_v)$ 降序排序。
令 $S_k$ = 前 $k$ 个的 $(f_v - g_v)$ 之和。
则当 $x = k$ 时，最大值 = $S_k + \sum_{v} g_v$。

这样对每个 $x$ 可以 $O(1)$ 得到最大值。

---

根节点处理

对于根 $r$，没有父亲边。
其 $x$ 表示子节点指向 $r$ 的个数。
贡献为：

$$\min(in'_r + x,\; out'_r + (c - x)) \cdot t_r$$

加上子节点的贡献。

---

最终答案

总初始疲劳 = $\sum \deg(i) \cdot t_i$。
总最大减少 = 对每个未定向连通块 DP 得到的最优减少之和（根节点的最佳情况）。
答案 = 总初始疲劳 − 总最大减少。

复杂度 $O(n \log n)$，来自排序。

---

示例验证（样例1）

$n=5$
$t = [40,10,30,50,20]$
$h = [2,3,2,3,1]$

边：
$(1,2): h_1=2,h_2=3 \Rightarrow 1\to 2$
$(1,3): h_1=2,h_3=2 \Rightarrow$ 未定
$(2,4): h_2=3,h_4=3 \Rightarrow$ 未定
$(2,5): h_2=3,h_5=1 \Rightarrow 5\to 2$（因为 $h_5 < h_2$）

未定向边构成两个连通块：$\{1,3\}$ 和 $\{2,4\}$。

初始总疲劳 = $\sum \deg(i)t_i = 2\cdot40 + 3\cdot10 + 1\cdot30 + 1\cdot50 + 1\cdot20 = 80+30+30+50+20=210$。

DP 后最大减少 = $50$，答案 = $210-50=160$，与输出一致。