U563922 BUY on cactus

成长：[static tree](http://poj.org/problem?id=3728) $\Rightarrow$ dynamic cactus。

小 Y 来到一棵 $n$ 个点 $m$ 条边的仙人掌上旅游，并希望通过买卖赚差价，点编号为 $1\sim n$。 在一次旅游时，她告诉你旅游的起点和终点 $u,v$。她会选择一条以 $u,v$ 为端点的**简单路径**，并在路上选择一个结点 $u'$，花费 $c_{u'}$ 的代价购入某个物品，再选择一个结点 $v'$，以 $w_{v'}$ 的价格卖出，获得 $w_{v'}-c_{u'}$ 的利润。显然她必须先购入才能卖出，但 $u'$ 可以等于 $v'$。她不能啥也不做。小 Y 问你，在最优计划下，她能够获得的利润最大值，这个值可能为负。 由于这棵仙人掌很不稳定，每一个点的 $c_u,w_u$ 都可能发生变化。你需要支持这种修改的同时，能够回答小 Y 的问题。具体来说，总共有 $q$ 次修改或询问，每次格式如下： - $1\ u\ v$：表示一次查询。 - $2\ u\ v\ t$：表示一次修改，若 $t=0$，将 $c_u\gets v$，否则将 $w_u\gets v$。 **简单路径**指每个结点最多出现一次的路径。

第一行两个整数 $n,m$。 接下来 $m$ 行，每行两个整数 $u,v$，表示 $u,v$ 之间有一条边。 接下来一行 $n$ 个整数，第 $i$ 个整数 $c_i$ 表示在 $i$ 购入的代价。 接下来一行 $n$ 个整数，第 $i$ 个整数 $w_i$ 表示在 $i$ 卖出的收益。 接下来一行一个整数 $q$，表示询问次数。 接下来 $q$ 行，每行两个整数或四个整数描述一次修改或询问。

若干行，每行一个整数，表示每次询问的答案。

样例一第三次询问解释：选择简单路径 $2\rightarrow5\rightarrow3\rightarrow6\rightarrow10$，在 $5$ 花费 $c_5=-11$ 购入，在 $3$ 获得 $w_3=19$，利润 $w_3-c_5=19-(-11)=30$。路径不唯一，例如 $2\rightarrow5\rightarrow3\rightarrow6\rightarrow4\rightarrow10$ 也是一条可能的简单路径。 $2\leq n\leq2\times10^5$，熟悉仙人掌的同学应该不需要 $m$ 的范围（$n-1\leq m\leq2n-2$）。$1\leq q\leq 10^5$。任意时刻 $|c_i|,|w_i|\leq5\times10^8$。$t\in\{0,1\}$。 对于零个测试点，$q=0$。 对于一个测试点，$n,q\leq20$。 对于另一个测试点，$n,q\leq1000$。 对于另一个测试点，$m=n-1$，没有修改操作，$c_i=w_i$。 对于另一个测试点，$m=n-1$。 对于另一个测试点，没有修改操作。 对于另一个测试点，$m=n$。 我的博文 & 题解：[《圆方树学习笔记 —— 一种关于点双连通分量的思考方式》](https://www.cnblogs.com/XuYueming/p/18313014)。