U184872 乖龙(树 2)

背景搬到了[剪切板](https://www.luogu.com.cn/paste/1j57htwr)有兴趣的可以去看

这一次 出逃的乖龙躲到了一棵树上 但是这棵树很特殊 这棵树有 $n$ 个节点 由 $n - 1$ 条边连接 每个点有一个蓄雷值 同时每一条边有一个电导因子 雷神会不时的放出电击强度为 $x$ 电导强度为 $y$ 的雷电攻击这棵树 使得某个节点的蓄雷值增加 对于每一次雷击 假设击中 $u$ 点 在 $u$ 点的子树中的一个节点 $v$ 如果 $(u, v)$ 上所有边的导电因子都大于等于 $y$ 则 $u$ 点的权值会增加 $x$ **如果多个点满足 则会增加多次** 现在乖龙会不时的询问你某个点的蓄雷值以确定自己最好的躲藏位置 对于乖龙的每次询问 你需要给出回答

第一行两个正整数 $n, q$ 表示树的节点个数以及电击与询问的次数 第二行空格分开的 $n$ 个数 第 $i$ 个数 $val_i$ 表示 $i$ 号点的初始蓄雷值 接下来 $n - 1$ 行每行三个数 $u, v, w$ 表一一条连接 $u$ 点和 $v$ 点的电导虚边 接下来的 $q$ 行 每行若干数 第一个数 $opt$ 若 $opt = 1$ 接下来有一个数 $u$ 表示乖龙询问 $u$ 点的蓄雷值 若 $opt = 2$ 接下来三个数 $x, y, u$ 表示雷神放出的电击强度 $x$ 电导强度为 $y$ 的雷电击中了 $u$ 点

对于每一个操作 $1$ 输出一行一个整数表示你对乖龙的询问作出的回答

对于 $30\%$ 的数据 $1 \leq n, q \leq 2 \times 10^3$ 对于另 $20\%$ 的数据 树随机生成 对于另 $20\%$ 的数据 数的形态为一条链 对于 $100\%$ 的数据 $1 \leq n, q \leq 10^5, 1 \leq w \leq 10^5, 1 \leq x, y \leq 10^5, 1 \leq val_i \leq 10^5, 1 \leq u \leq n$ --- 　　乖龙被雷神带走了，就在飞鱼村村外的竹林里。 　　在主动通知雷神之前，它要求桃夭他们把它装在竹篓里，再次去到了阿忙家。 　　它没有进去，只站在门口远远看了看那片在春风中摇摆的甘蔗苗，阿忙正拎着水桶，小心翼翼地用木勺往地里浇水，十岁男孩的小脸上充满了幸福跟期待，满头白发的老奶奶坐在不远处的躺椅里，边晒太阳边嘱咐他小心些。 　　离开时，乖龙在竹篓里说了一句“他种得太辛苦了，要是一夜间都没了，怪伤心的。” 　　竹林里，黑冠黑衣，高窈健硕的雷神从天而降，面无表情地看着它，伸出手“回去吧。” 　　乖龙老老实实地跳到了他的手掌里。 　　桃夭全程盯着雷神，在他离开前突然叫住了他。 　　“有何贵干”雷神看着这个貌不惊人的小丫头。 　　她仰头道“我是桃都来的桃夭。” 　　“原来是鬼医桃夭。”雷神点点头，“不过我与桃都素无往来。你不在桃都，跑到人界游荡，本也不关我的事，但还是提醒一句，来了人界便要守人界的规矩，若有行差踏错，落到我手里也不是好过的。” 　　桃夭黑着脸道“我呢，就不劳大神你操心了，桃都的人自然有桃都的规矩。我叫住你，也是想提醒你，以后别动不动就拿雷乱劈，你有嘴，可以讲道理的。实在要劈谁，麻烦也看清楚他旁边有没有无辜百姓。” 　　雷神打量她一番，摇头一笑，走了，连句回应都懒得给她。 　　就在她的脸色难看得能掐出水时，雷神突然站住，回头道“你以为，在我不允许的情况下，乖龙真的能一次又一次逃脱你以为，在我不愿意的情况下，乖龙能想受伤就受伤你以为，你们真是命大死不了” 　　桃夭一愣。 　　雷神浅浅一笑“神也罢人也好，总有那么一段长不大想不开的时候，过去了就好。”说着他又想起了什么，看了看自己的袖口，里头装着瘫痪的旱仙，笑道，“有些小仙的过分行为我也略有耳闻，让他们吃些苦头倒也无所谓。” 　　桃夭脱口而出“你什么都知道包括乖龙想出了这个阻止旱仙的法子” 　　雷神笑而不语，转身离去。 　　“喂，你别太折磨乖龙”桃夭在后头大喊，“它很乖，而且比谁都更像个称职的神仙。” 　　这时，乖龙从雷神手掌里探出脑袋来，挥着爪子跟她说“回去吧，别惦记我，我不乖。” 　　金光闪过，雷神与乖龙再无迹可寻。