题解
一眼就是线段树维护点分树的dfs序嘛
代码debug一年（手动再见）
码力直线下降，坐等滚粗= =
很明显的我们需要一个点分树，然后求出以每个重心为根的树的dfs序，线段树维护一下每个点的价值-每个点到根的距离
对于修改点直接单点修改，对于边相当于修改了一个子树到根的距离，就是dfs序上一段区间的加减
然后查询点分树里除掉这个点所在子树的区间，查询两边区间的最大值即可
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#define enter putchar('
')
#define space putchar(' ')
#define MAXN 100005
#define mp make_pair
#define pb push_back
#define fi first
#define se second
//#define ivorysi
using namespace std;
typedef long long int64;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int Line[MAXN],idx;
int64 D[MAXN];
pair<int64,int> Max(pair<int64,int> a,pair<int64,int> b) {
if(a.fi != b.fi) return a.fi < b.fi ? b : a;
else return a.se < b.se ? a : b;
}
struct Segment_Tree {
struct Tr_node {
int L,R,lc,rc;
int64 lazy;
pair<int64,int> S;
}tr[MAXN * 40];
int Ncnt;
#define lc(u) tr[u].lc
#define rc(u) tr[u].rc
void update(int u) {
tr[u].S = Max(tr[lc(u)].S,tr[rc(u)].S);
}
void addlazy(int u,int64 v) {
tr[u].S.fi += v;
tr[u].lazy += v;
}
void pushdown(int u) {
if(tr[u].lazy) {
addlazy(lc(u),tr[u].lazy);
addlazy(rc(u),tr[u].lazy);
tr[u].lazy = 0;
}
}
void build(int &u,int L,int R) {
u = ++Ncnt;
tr[u].L = L;tr[u].R = R;
if(L == R) {
tr[u].S = mp(D[Line[L]],Line[L]);
return;
}
int mid = (L + R) >> 1;
build(tr[u].lc,L,mid);
build(tr[u].rc,mid + 1,R);
update(u);
}
void Add(int u,int l,int r,int64 v) {
if(tr[u].L == l && tr[u].R == r) {addlazy(u,v);return;}
int mid = (tr[u].L + tr[u].R) >> 1;
pushdown(u);
if(r <= mid) Add(lc(u),l,r,v);
else if(l > mid) Add(rc(u),l,r,v);
else {Add(lc(u),l,mid,v),Add(rc(u),mid + 1,r,v);}
update(u);
}
pair<int64,int> Query(int u,int l,int r) {
if(r < l) return mp(-1e18,-1);
if(tr[u].L == l && tr[u].R == r) return tr[u].S;
pushdown(u);
int mid = (tr[u].L + tr[u].R) >> 1;
if(r <= mid) return Query(lc(u),l,r);
else if(l > mid) return Query(rc(u),l,r);
else return Max(Query(lc(u),l,mid),Query(rc(u),mid + 1,r));
}
}SegTr;
struct node {
int to,next;int64 val;
}E[MAXN * 2];
int head[MAXN],sumE;
void add(int u,int v,int64 c) {
E[++sumE].to = v;
E[sumE].next = head[u];
E[sumE].val = c;
head[u] = sumE;
}
struct PointDivideTree {
vector<int> Fa,dfn,aux,siz;
vector<int64> Fa_dis;
int rt;
}PD[MAXN];
int N,Q;
int64 z[MAXN];
bool vis[MAXN];
int siz[MAXN],son[MAXN],fa[MAXN];
int que[MAXN],ql,qr;
int calcG(int st) {
ql = 1,qr = 0;
que[++qr] = st;fa[st] = 0;
while(ql <= qr) {
int u = que[ql++];
siz[u] = 1;son[u] = 0;
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(!vis[v] && fa[u] != v) {
fa[v] = u;
que[++qr] = v;
}
}
}
int res = que[qr];
for(int i = qr ; i >= 1 ; --i) {
int u = que[i];
son[u] = max(son[u],qr - siz[u]);
if(son[u] < son[res]) res = u;
siz[fa[u]] += siz[u];
if(siz[u] > son[fa[u]]) son[fa[u]] = siz[u];
}
return res;
}
int Calc(int u,int fa,int64 fa_dis,int G) {
int s = 1;
++idx;
Line[idx] = u;
D[u] = D[fa] + fa_dis;
PD[u].aux.pb(G);
PD[u].Fa.pb(fa);
PD[u].dfn.pb(idx);
PD[u].Fa_dis.pb(fa_dis);
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(!vis[v] && v != fa) {
s += Calc(v,u,E[i].val,G);
}
}
PD[u].siz.pb(s);
return s;
}
void pre(int u) {
int G = calcG(u);
vis[G] = 1;
idx = 0;D[G] = 0;
Calc(G,0,0,G);
for(int i = 1 ; i <= idx ; ++i) D[Line[i]] = z[Line[i]] - D[Line[i]];
SegTr.build(PD[G].rt,1,idx);
for(int i = head[G] ; i ; i = E[i].next) {
int v = E[i].to;
if(!vis[v]) pre(v);
}
}
void Init() {
read(N);read(Q);
for(int i = 1 ; i <= N ; ++i) read(z[i]);
int u,v;int64 c;
for(int i = 1 ; i < N ; ++i) {
read(u);read(v);read(c);
add(u,v,c);add(v,u,c);
}
pre(1);
}
void Solve() {
int op,u,v;
int64 w;
int st = 1;
for(int q = 1 ; q <= Q ; ++q) {
read(op);
if(op == 1) {
read(u);read(w);
int s = PD[u].aux.size();
for(int i = 0 ; i < s ; ++i) {
int G = PD[u].aux[i];
SegTr.Add(PD[G].rt,PD[u].dfn[i],PD[u].dfn[i],w - z[u]);
}
z[u] = w;
}
else {
read(u);read(v);read(w);
int s = min(PD[u].aux.size(),PD[v].aux.size());
for(int i = 0 ; i < s ; ++i) {
int rt = PD[PD[u].aux[i]].rt;
if(PD[u].Fa[i] == v) {
SegTr.Add(rt,PD[u].dfn[i],PD[u].dfn[i] + PD[u].siz[i] - 1,PD[u].Fa_dis[i] - w);
PD[u].Fa_dis[i] = w;
}
else if(PD[v].Fa[i] == u) {
SegTr.Add(rt,PD[v].dfn[i],PD[v].dfn[i] + PD[v].siz[i] - 1,PD[v].Fa_dis[i] - w);
PD[v].Fa_dis[i] = w;
}
else break;
}
}
pair<int64,int> p = mp(-1e18,-1);
int s = PD[st].aux.size();
for(int i = 0 ; i < s; ++i) {
int G = PD[st].aux[i],rt = PD[G].rt;
int64 t = -SegTr.Query(rt,PD[st].dfn[i],PD[st].dfn[i]).fi + z[st];
pair<int64,int> k;
if(i != s - 1) k = Max(SegTr.Query(rt,1,PD[st].dfn[i] - 1),SegTr.Query(rt,PD[st].dfn[i] + PD[st].siz[i],PD[G].siz[i]));
else k = SegTr.Query(rt,2,PD[G].siz[i]);
if(k.se == -1) continue;
p = Max(p,mp(k.fi - t,k.se));
}
st = p.se;
out(st);space;
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
Solve();
}