prologue
还是太菜了，这个 154 行的树剖20min才敲完。
analysis
首先，处理这个给到我们的这个式子。
\[\max(\mid a _ u + a _ v \mid, \mid a _ u - a _ v \mid)
\]
我们可以分类讨论：
-
\(a > 0, b > 0\):
显然 \(a + b > a - b\), 所以上式等于 $a + b \Rightarrow \mid a \mid + \mid b \mid $ -
\(a > 0, b < 0 \iff a < 0, b > 0\)
这个时候，我们只需要讨论 \(a > 0, b < 0\) 的情况就好了。我们将 \(b\) 的符号拿出来，\(\Rightarrow a - (- \mid b \mid) \Rightarrow a + \mid b \mid \Rightarrow \mid a \mid + \mid b \mid\) -
\(a < 0, b < 0\)
操作同上， $ \mid -(\mid a \mid + \mid b \mid) \mid \Rightarrow \mid a \mid + \mid b \mid $。
综上：
\[\max(\mid a _ u + a _ v \mid, \mid a _ u - a _ v \mid) \iff \mid a \mid + \mid b \mid
\]
对于一条路径的询问，我们把每两个点之间的距离拿出来，不断累加，就可以知道，这一段路径的长度就是下式。（其中 \(dis _ {u \to v}\) 表示从 \(u\) 到 \(v\) 的距离， \(sum _ {u \to v}\) 表示从 \(u\) 到 \(v\) 的点值的绝对值之和，\(w_u\) 和 \(w_v\) 表示这两个点的点权）
\[dis _ {u \to v} = 2 \cdot sum _ {u \to v} - \mid w_u \mid - \mid w_v \mid
\]
之后就是正常实现一个树链剖分和线段树即可。
code time
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rl register ll
const ll N = 1e5 + 10, M = N << 1;
ll n, m;
ll tot, ne[M], e[M], h[N], w[N];
ll son[N], top[N], id[N], cnt, fa[N], dep[N], nw[N], sz[N];
struct node
{
ll l, r;
ll dis;
}tr[N << 2];
inline void add(ll a, ll b)
{
ne[++tot] = h[a], h[a] = tot, e[tot] = b;
}
inline void dfs1(ll u, ll fath, ll depth)
{
fa[u] = fath, dep[u] = depth, sz[u] = 1;
for(rl i=h[u]; ~i; i = ne[i])
{
ll v = e[i];
if(v == fath) continue;
dfs1(v, u, depth + 1);
sz[u] += sz[v];
if(sz[son[u]] < sz[v]) son[u] = v;
}
}
inline void dfs2(ll u, ll t)
{
id[u] = ++ cnt, nw[cnt] = w[u], top[u] = t;
if(!son[u]) return ;
dfs2(son[u], t);
for(rl i=h[u]; ~i; i = ne[i])
{
ll v = e[i];
if(v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
inline void pushup(ll u)
{
tr[u].dis = abs(tr[u << 1].dis) + abs(tr[u << 1 | 1].dis);
}
inline void build(ll u, ll l, ll r)
{
tr[u] = {l, r, abs(nw[r])};
if(l == r) return ;
ll mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
inline void update(ll u, ll l, ll r, ll k)
{
if(tr[u].l == l && tr[u].l == tr[u].r)
{
tr[u].dis = k;
return ;
}
ll mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) update(u << 1, l, r, k);
if(r > mid) update(u << 1 | 1, l, r, k);
pushup(u);
}
inline ll query(ll u, ll l, ll r)
{
ll res = 0;
if(l <= tr[u].l && r >= tr[u].r) return tr[u].dis;
ll mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) res += query(u << 1, l, r);
if(r > mid) res += query(u << 1 | 1, l, r);
return res;
}
inline void upd_point(ll u, ll k)
{
update(1, id[u], id[u], k);
}
inline ll query_path(ll u, ll v)
{
ll res = - query(1, id[u], id[u]) - query(1, id[v], id[v]);
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]]) swap(u, v);
res += 2 * query(1, id[top[u]], id[u]);
u = fa[top[u]];
}
if(dep[u] < dep[v]) swap(u, v);
res += 2 * query(1, id[v], id[u]);
return res;
}
int main()
{
// freopen("1.in", "r", stdin), freopen("1.out", "w", stdout);
cin >> n >> m;
memset(h, -1, sizeof h);
for(rl i=1; i <= n; ++ i) cin >> w[i];
for(rl i=1; i < n; ++ i)
{
ll a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs1(1, -1, 1);
dfs2(1, 1);
build(1, 1, n);
while(m -- )
{
ll t, u, v;
cin >> t >> u >> v;
if(t == 1) upd_point(u, abs(v));
else cout << query_path(u, v) << endl;
}
return 0;
}