U648394 异世界树形网络调度模拟

# 有没有大犇会做这道题，我自己想了个大模拟，但不会打……三个小样例是对的 ## 有大犇做出来了可以私我 ## 有大犇出好了大样例也可以私我 ~~为了放题~~输出HELP即可AC了 做出标程和出好大样例私我的，（两个的）**前三名有奖** 在异世界的魔法网络中，有 $n$ 个魔法节点通过 $n-1$ 条魔法通道连接成一棵树。 每个节点都有一个 **魔法值** $a_i$（可能为负数）和一个 **魔法类型** $t_i \in {1,2,3}$。 魔法网络需要处理 $q$ 次 **时空扭曲事件**，每次事件会引发复杂的连锁反应，需要你进行**精确模拟**。

## - 初始状态 - 一棵 $n$ 个节点的树，节点编号 $1$ 到 $n$。 - 每个节点 $i$ 有： - 魔法值 $a_i$（$-10^9 \le a_i \le 10^9$） - 魔法类型 $t_i \in {1,2,3}$ - 每条边有一个 通道容量 $c_e$（$1 \le c_e \le 10^9$） ## 事件类型 - 有 $5$ 种事件，共 $q$ 次： - 1.节点魔法值变化：1 u x 节点 $u$ 的魔法值增加 $x$（$-10^9 \le x \le 10^9$） - 2.节点类型切换：2 u k 节点 $u$ 的类型变为 $k$（$k \in {1,2,3}$） - 3.通道容量变化：3 u v w 边 $(u,v)$ 的容量变为 $w$（$1 \le w \le 10^9$） - 4.局部平衡重构：4 u 以 $u$ 为根，对子树进行 魔法流平衡操作（见下文） - 5.全局能量汇聚：5 对整个树进行 跨维度能量汇聚（见下文） --- ## 核心操作说明 **魔法流平衡操作（事件4）** 设以 $u$ 为根的子树为 $S$： 1. 在 $S$ 内部构建一个 **虚拟流网络**： - 源点：$S$ 中所有 $t_i=1$ 的节点 - 汇点：$S$ 中所有 $t_i=2$ 的节点 - 中转点：$S$ 中所有 $t_i=3$ 的节点 - 边：原树中 $S$ 内的所有边，容量为 $c_e$ 2. 计算从所有源点到所有汇点的 **最大可能总流量** $F$（多源多汇） 3. 按照以下规则更新 $S$ 中节点的魔法值： - 每个源点流出的总流量不能超过其魔法值（源点魔法值减少） - 每个汇点流入的总流量增加其魔法值 - 中转点不消耗也不增加魔法值，只转发流量 - 如果流量 $F$ 超过源点总魔法值，则按比例分配 4.最终，$S$ 中所有 $t_i=2$ 的节点会记录 **累计吸收量** $B_i$（用于事件5） --- ## 跨维度能量汇聚（事件5） 1. 对整棵树进行 **分层拓扑聚合**： - 从叶子节点开始，每层节点将其 **累计吸收量** $B_i$传递给父节点 - 传递时，父节点接收的值 = $\min\left(\text{子节点传递值}, c_e \times \text{当前深度}\right)$ 2. 最终根节点（节点1）获得一个 **聚合能量值** $E$ 3. $E$ 会与所有节点的魔法值产生 **量子纠缠**： - 最终结果 $R = E \times \sum_{i=1}^n \left[ a_i \times (d_i+1) \right]$ - 其中 $d_i$ 是节点 $i$ 的深度（根节点深度为0） 4. 输出 $R$ 的值（**可能非常大，需要高精度**）

第一行两个整数 $n, q$（$1 \le n \le 2\times 10^5, 1 \le q \le 10^5$） 第二行 $n$ 个整数 $a_1, a_2, ..., a_n$ 第三行 $n$ 个整数 $t_1, t_2, ..., t_n$ 接下来 $n-1$ 行，每行三个整数 $u, v, c$，表示边和容量 接下来 $q$ 行，每行一个事件，格式如上所述

对于每个 **事件5**，输出一行，表示 $R$ 的值。 由于 $R$ 可能非常大，输出时： - 如果 $R < 10^{100}$，直接输出十进制值 - 否则输出科学计数法：x.xxx...e+xxx - 保留100位有效数字（四舍五入） - 指数部分输出十进制

``` ## 样例说明： 这些样例数据经过精心设计，可以测试各种边界情况： - 样例1：测试基本的事件4和5逻辑 - 样例2：测试类型切换对网络流的影响 - 样例3：测试所有事件类型的组合，包括边容量变化 --- ## 样例3解释： **1. 初始状态** ``` 节点: 1 2 3 4 5 6 7 a_i: 5 -3 2 4 -1 6 3 t_i: 1 2 3 1 2 3 1 边容量: 1-2:12, 2-3:9, 2-4:7, 3-5:5, 3-6:8, 5-7:6 ``` **2 .事件序列执行过程：** 1. 事件1: 1 4 2 - 节点4的魔法值: 4 → 6 - 状态更新: a[4] = 6 2. 事件2: 2 5 1 - 节点5的类型: 2(汇点) → 1(源点) - 状态更新: t[5] = 1 3. 事件3: 4 3 (以节点3为根的子树平衡) 子树包含节点: 3,5,6,7 - 源点: 节点5(a=-1), 节点7(a=3) 总魔法值=2 - 汇点: 无 (节点3是中转点，节点6是中转点) - 流量F=0，无变化 - 节点5,7的B值不变 4. 事件4: 3 2 4 15 - 边(2,4)容量: 7 → 15 - 更新边容量 5. 事件5: 4 2 (以节点2为根的子树平衡) 子树: 2,3,4,5,6,7 - 源点: 节点4(a=6,t=1), 节点5(a=-1,t=1), 节点7(a=3,t=1) 总魔法值=8 - 汇点: 节点2(a=-3,t=2) - 中转点: 节点3(t=3), 节点6(t=3) - 最大流量F = min(8, 到节点2的路径容量) = 8 - 更新: - 源点魔法值耗尽: a4=0, a5=-9, a7=-5 - 汇点节点2: a2从-3变为5, B2增加8 - B2累计值=8 6. 事件6: 5 (第一次全局能量汇聚) - 分层拓扑聚合: - 叶子→父节点传递B值 - 节点4(B=0)→2: min(0,15×2)=0 - 节点7(B=0)→5→3→2: 路径传递计算 - 节点6(B=0)→3→2 - 最终根节点1获得E值 - 量子纠缠计算: - 深度: d1=0,d2=1,d3=2,d4=2,d5=3,d6=2,d7=4 - 当前a值: [5,5,2,0,-9,6,-5] - 求和 = 5×1 + 5×2 + 2×3 + 0×3 + (-9)×4 + 6×3 + (-5)×5 = 5 + 10 + 6 + 0 - 36 + 18 - 25 = -22 - R = E × (-22) = -720 7. 事件7: 1 7 -3 - 节点7魔法值: -5 → -8 8. 事件8: 2 1 3 - 节点1类型: 1(源点) → 3(中转点) 9. 事件9: 4 1 (整棵树平衡) - 源点: 节点4(a=0), 节点5(a=-9), 节点7(a=-8) 总魔法值=-17 - 汇点: 节点2(a=5,t=2) - 由于源点总魔法值为负，流量F=0，无变化 - B值不变 10. 事件10: 5 (第二次全局汇聚) - E值重新计算 - a值求和 = 5×1 + 5×2 + 2×3 + 0×3 + (-9)×4 + 6×3 + (-8)×5 = 5 + 10 + 6 + 0 - 36 + 18 - 40 = -37 - R = E × (-37) = 1512 ### 关键点： 1. 负数魔法值会影响流量计算 2. 类型切换改变网络结构 3. 边容量变化影响传递限制 4. 全局汇聚的E值通过分层聚合计算 --- ``` ## 数据范围 - 30%：$n, q \le 1000$，事件**只有类型4和5** - 50%：$n, q \le 50000$，**没有类型3事件** - 70%：$n, q \le 10^5$，结果**不需要**高精度 - 100%：全范围，结果**需要**高精度 --- ## 时空限制 - 时间：3.0秒 - 内存：512MB --- - 事件4的流量计算可以使用树形DP+贪心 - 事件5的传递需要自底向上分层处理 - 高精度建议使用压位+FFT优化乘法 - 注意负数处理和科学计数法转换 - 实际数据保证中途结果不超过 $10^{1000}$