CF838B Diverging Directions

给定一个有 $n$ 个点、$2n-2$ 条边的有向带权图。点编号为 $1$ 到 $n$，边编号为 $1$ 到 $2n-2$。这些边可以分为两部分： - 前 $n-1$ 条边形成一棵以 $1$ 号点为根的有根生成树，所有这些边都从根指向子节点。 - 后 $n-1$ 条边均为从节点 $i$ 到节点 $1$ 的边，$2\leq i\leq n$。 你将会得到 $q$ 组询问。每种询问有两类： - $1\ i\ w$：将第 $i$ 条边的权值修改为 $w$。 - $2\ u\ v$：输出从点 $u$ 到点 $v$ 的最短路径长度。 请你对于每一个第 2 种类型的询问，输出最短路径的长度。

第一行输入两个正整数 $n, q$（$2\leq n, q\leq 200000$），分别表示点数和询问数。 接下来 $2n-2$ 行，每行包含三个整数 $a_i, b_i, c_i$，表示一条从 $a_i$ 指向 $b_i$，权值为 $c_i$ 的有向边。 前 $n-1$ 行描述一棵以 $1$ 为根的、有向的生成树，边的方向都从根指向其它节点。后 $n-1$ 行的 $b_j=1$，也就是说从 $a_j$（$2\leq a_j\leq n$，且两两不同）指向 $1$。 接下来 $q$ 行，每行三个整数，描述如上所述的一个询问。 所有边权均在 $1$ 到 $10^6$ 之间。

对于每一个类型为 $2$ 的询问，输出一行，对应起点 $u$ 到终点 $v$ 的最短路径长度。

由 ChatGPT 5 翻译