// Tot ce trebuie codat: cele 7 linii din LazySegmentTree marcate cu //
// si main-ul de 25 de linii. Restul e pur si simplu copy-paste
#include <bits/stdc++.h>
using namespace std;
class LazySegmentTree {
public:
struct Node {
int val; //
Node() : //
val(numeric_limits<int> :: min()) {}; //
Node (int _val) : //
val(_val) {}; //
} *sgt; static const Node nul;
int siz, _lef, _rig; bool idx0;
void updateLazy(int nod, int lef, int rig) {
}
Node mergeSons(Node son1, Node son2) {
return Node(max(son1.val, son2.val)); } //
template <typename type>
void updateNode(int nod, int lef, int rig, type val) {
sgt[nod] = val; //
updateLazy(nod, lef, rig); }
inline int findPos(const int lef, const int rig) {
return (lef + rig) | (lef != rig); }
template <typename type>
void _buildTree(int nod, int lef, int rig, type arr[]) {
if (lef == rig) {
updateNode(nod, lef, rig, arr[lef - idx0]); }
else {
int mid = (lef + rig) >> 1,
lefSon = findPos(lef, mid),
rigSon = findPos(mid + 1, rig);
_buildTree(lefSon, lef, mid, arr);
_buildTree(rigSon, mid + 1, rig, arr);
sgt[nod] = mergeSons(sgt[lefSon], sgt[rigSon]); } }
template <typename type>
void _updateTree(int nod, int lef, int rig, type val) {
if (_lef <= lef and rig <= _rig) {
updateNode(nod, lef, rig, val); }
else {
int mid = (lef + rig) >> 1,
lefSon = findPos(lef, mid),
rigSon = findPos(mid + 1, rig);
updateLazy(lefSon, lef, mid);
updateLazy(rigSon, mid + 1, rig);
if (_lef <= mid) {
_updateTree(lefSon, lef, mid, val); }
if (mid < _rig) {
_updateTree(rigSon, mid + 1, rig, val); }
sgt[nod] = mergeSons(sgt[lefSon], sgt[rigSon]); } }
Node _queryTree(int nod, int lef, int rig) {
if (_lef <= lef and rig <= _rig) {
return sgt[nod]; }
else {
int mid = (lef + rig) >> 1,
lefSon = findPos(lef, mid),
rigSon = findPos(mid + 1, rig);
updateLazy(lefSon, lef, mid);
updateLazy(rigSon, mid + 1, rig);
if (_rig <= mid) {
return _queryTree(lefSon, lef, mid); }
if (mid < _lef) {
return _queryTree(rigSon, mid + 1, rig); }
return mergeSons(_queryTree(lefSon, lef, mid),
_queryTree(rigSon, mid + 1, rig)); } }
int _findFirstKnow(int nod, int lef, int rig, std::function<bool(Node&)> &good) {
if (lef == rig) {
return lef; }
else {
int mid = (lef + rig) >> 1,
lefSon = findPos(lef, mid),
rigSon = findPos(mid + 1, rig);
updateLazy(lefSon, lef, mid);
updateLazy(rigSon, mid + 1, rig);
if (good(sgt[lefSon])) {
return _findFirstKnow(lefSon, lef, mid, good); }
else {
return _findFirstKnow(rigSon, mid + 1, rig, good); } } }
int _findFirst(int nod, int lef, int rig, std::function<bool(Node&)> &good) {
if (_lef <= lef and _rig <= rig) {
return good(sgt[nod]) ? _findFirstKnow(nod, lef, rig, good) : -1; }
else {
int mid = (lef + rig) >> 1, res = -1,
lefSon = findPos(lef, mid),
rigSon = findPos(mid + 1, rig);
updateLazy(lefSon, lef, mid);
updateLazy(rigSon, mid + 1, rig);
if (_lef <= mid) {
res = _findFirst(lefSon, lef, mid, good); }
if (mid < _rig and res == -1) {
res = _findFirst(rigSon, mid + 1, rig, good); }
return res; } }
int _findLastKnow(int nod, int lef, int rig, std::function<bool(Node&)> &good) {
if (lef == rig) {
return lef; }
else {
int mid = (lef + rig) >> 1,
lefSon = findPos(lef, mid),
rigSon = findPos(mid + 1, rig);
updateLazy(lefSon, lef, mid);
updateLazy(rigSon, mid + 1, rig);
if (good(sgt[rigSon])) {
return _findLastKnow(rigSon, mid + 1, rig, good); }
else {
return _findLastKnow(lefSon, lef, mid, good); } } }
int _findLast(int nod, int lef, int rig, std::function<bool(Node&)> &good) {
if (_lef <= lef and _rig <= rig) {
return good(sgt[nod]) ? _findLastKnow(nod, lef, rig, good) : -1; }
else {
int mid = (lef + rig) >> 1, res = -1,
lefSon = findPos(lef, mid),
rigSon = findPos(mid + 1, rig);
updateLazy(lefSon, lef, mid);
updateLazy(rigSon, mid + 1, rig);
if (mid < _rig) {
res = _findLast(rigSon, mid + 1, rig, good); }
if (_lef <= mid and res == -1) {
res = _findLast(lefSon, lef, mid, good); }
return res; } }
public:
LazySegmentTree(int _siz, bool _idx0 = false) : siz(_siz), idx0(_idx0) {
sgt = new Node[siz << 1]; }
void resizeTree(int _siz) {
siz = _siz; }
template <typename type>
void buildTree(type *arr) {
_buildTree(1, 1, siz, arr); }
template <typename type>
void updateTree(int lef, int rig, type val = nul) {
_lef = lef + idx0; _rig = rig + idx0;
_updateTree(1, 1, siz, val); }
Node queryTree(int lef, int rig) {
_lef = lef + idx0; _rig = rig + idx0;
return _queryTree(1, 1, siz); }
int findFirst(int lef, int rig, std::function<bool(Node&)> good) {
_lef = lef + idx0; _rig = rig + idx0;
return _findFirst(1, 1, siz, good); }
int findLast(int lef, int rig, std::function<bool(Node&)> good) {
_lef = lef + idx0; _rig = rig + idx0;
return _findLast(1, 1, siz, good); }
};
template <typename type>
class Graph {
public:
struct Edge {
int from, to;
type cost;
};
int n;
vector<Edge> edg;
vector<vector<int>> gph;
Graph(int _n) : n(_n) {
gph.resize(n); }
virtual int addEdge(int from, int to, type cost = 1) = 0;
};
template <typename type>
class Forest : public Graph<type> {
public:
using Graph<type> :: n;
using Graph<type> :: edg;
using Graph<type> :: gph;
Forest(int _n) :
Graph<type>(_n) {}
int addEdge(int from, int to, type cost = 1) {
assert(0 <= min(from, to) and max(from, to) < n);
int id = (int) edg.size();
gph[from].push_back(id); gph[to].push_back(id);
edg.push_back({from, to, cost});
return id; }
};
template <typename type>
class DfsForest : public Forest<type> {
public:
using Forest<type> :: n;
using Forest<type> :: edg;
using Forest<type> :: gph;
vector<int> prv, pre, ord, pos,
end, szt, rot, dpt;
vector<type> dst;
DfsForest(int _n) :
Forest<type>(_n) {}
void initialize(void) {
prv = pre = pos = end = rot = dpt = vector<int>(n, -1);
szt = vector<int>(n, 0); dst = vector<type>(n); ord.clear(); }
void clear(void) {
prv.clear(); pre.clear(); ord.clear(); pos.clear(); end.clear();
szt.clear(); rot.clear(); dpt.clear(); dst.clear(); }
private:
void doDfs(int x) {
pos[x] = (int) ord.size(); ord.push_back(x); szt[x] = 1;
for (int id : gph[x]) {
if (id == pre[x]) {
continue; }
auto &ed = edg[id]; int y = ed.from ^ ed.to ^ x;
dpt[y] = dpt[x] + 1; dst[y] = dst[x] + ed.cost;
prv[y] = x; pre[y] = id; rot[y] = rot[x] != -1 ? rot[x] : y;
doDfs(y); szt[x] += szt[y]; }
end[x] = (int) ord.size() - 1; }
void doDfsFrom(int x) {
dpt[x] = 0; dst[x] = type{}; rot[x] = x;
prv[x] = pre[x] = -1; doDfs(x); }
public:
void dfs(int x, bool cle = true) {
if (prv.empty()) {
initialize(); }
else {
if (cle) {
ord.clear(); } }
doDfsFrom(x); }
void dfsAll(void) {
initialize();
for (int x = 0; x < n; ++x) {
if (dpt[x] == -1) {
doDfsFrom(x); } } }
};
template <typename type>
class LcaForest : public DfsForest<type> {
public:
using DfsForest<type> :: n;
using DfsForest<type> :: edg;
using DfsForest<type> :: gph;
using DfsForest<type> :: prv;
using DfsForest<type> :: pos;
using DfsForest<type> :: end;
using DfsForest<type> :: dpt;
int hg;
vector<vector<int>> anc;
LcaForest(int _n) :
DfsForest<type>(_n) {}
void buildLca(void) {
assert(!prv.empty());
int mx = *max_element(dpt.begin(), dpt.end());
for (hg = 1; (1 << hg) <= mx; ++hg);
anc.resize(n);
for (int i = 0; i < n; ++i) {
anc[i].resize(hg);
anc[i][0] = prv[i]; }
for (int j = 1; j < hg; ++j) {
for (int i = 0; i < n; ++i) {
anc[i][j] = anc[i][j - 1] == -1 ? -1 : anc[anc[i][j - 1]][j - 1]; } } }
inline bool isAncestor(int x, int y) {
return (pos[x] <= pos[y] and end[y] <= end[x]); }
inline int lca(int x, int y) {
assert(!prv.empty());
if (isAncestor(x, y)) { return x; }
if (isAncestor(y, x)) { return y; }
for (int j = hg - 1; j >= 0; --j) {
if (anc[x][j] != -1 and !isAncestor(anc[x][j], y)) {
x = anc[x][j]; } }
return prv[x]; }
};
template <typename type>
class HldForest : public LcaForest<type> {
public:
using LcaForest<type> :: n;
using LcaForest<type> :: edg;
using LcaForest<type> :: gph;
using LcaForest<type> :: prv;
using LcaForest<type> :: szt;
using LcaForest<type> :: pos;
using LcaForest<type> :: ord;
using LcaForest<type> :: dpt;
using LcaForest<type> :: dfs;
using LcaForest<type> :: dfsAll;
using LcaForest<type> :: buildLca;
using LcaForest<type> :: lca;
vector<int> fst, vis;
HldForest(int _n) : LcaForest<type>(_n) {
vis.resize(n); }
void buildHld(const vector<int> &lst) {
for (int cnt = 0; cnt <= 1; ++cnt) {
if (lst.empty()) {
dfsAll(); }
else {
ord.clear();
for (int x : lst) {
dfs(x, false); } }
if (cnt == 1) {
break; }
for (int x = 0; x < n; ++x) {
if (gph[x].empty()) {
continue; }
int bsz = -1, bid = 0;
for (int i = 0; i < (int) gph[x].size(); ++i) {
int id = gph[x][i], y = edg[id].from ^ edg[id].to ^ x;
if (prv[y] == x and szt[y] > bsz) {
bsz = szt[y]; bid = i; } }
swap(gph[x][0], gph[x][bid]); } }
buildLca(); fst.resize(n);
for (int i = 0; i < n; ++i) {
fst[i] = i; }
for (int i = 0; i < n - 1; ++i) {
int x = ord[i], y = ord[i + 1];
if (prv[y] == x) {
fst[y] = fst[x]; } } }
void buildHld(int x) {
buildHld(vector<int>(1, x)); }
void buildHldAll(void) {
buildHld(vector<int>()); }
vector<pair<int, int>> getPath(int x, int y) {
vector<pair<int, int>> lst[2];
assert(!fst.empty()); int z = lca(x, y);
if (z == -1) {
return vector<pair<int, int>>(); }
for (int id = 0; id <= 1; ++id) {
int v = (id == 0 ? x : y);
while (v != z) {
if (dpt[fst[v]] <= dpt[z]) {
lst[id].push_back(make_pair(pos[z] + 1, pos[v])); break; }
lst[id].push_back(make_pair(pos[fst[v]], pos[v])); v = prv[fst[v]]; } }
vector<pair<int, int>> ans;
for (int i = 0; i < (int) lst[0].size(); ++i) {
ans.push_back(make_pair(lst[0][i].second, lst[0][i].first)); }
ans.push_back(make_pair(-1, pos[z]));
for (int i = (int) lst[1].size() - 1; i >= 0; --i) {
ans.push_back(make_pair(lst[1][i].first, lst[1][i].second)); }
return ans; }
bool applyOnPath(int x, int y, bool wlca, function<void(int, int, bool)> f) {
// f(x, y, true if path [x -> y] goes up, false otherwise)
assert(!fst.empty()); int z = lca(x, y), v, cnt;
if (z == -1) {
return false; }
v = x;
while (v != z) {
if (dpt[fst[v]] <= dpt[z]) {
f(pos[z] + 1, pos[v], true); break; }
f(pos[fst[v]], pos[v], true); v = prv[fst[v]]; }
if (wlca) {
f(pos[z], pos[z], false); }
v = y; cnt = 0;
while (v != z) {
if (dpt[fst[v]] <= dpt[z]) {
f(pos[z] + 1, pos[v], false); break; }
vis[cnt++] = v; v = prv[fst[v]]; }
for (int i = cnt - 1; i >= 0; --i) {
v = vis[i]; f(pos[fst[v]], pos[v], false); }
return true; }
};
const int DIM = 100005;
int arr[DIM];
LazySegmentTree sgt(DIM, true);
HldForest<int> tree(DIM);
int main(void) {
freopen("heavypath.in", "r", stdin);
freopen("heavypath.out", "w", stdout);
int n, q, val; cin >> n >> q; sgt.resizeTree(n + 1);
function<void(int, int, bool)> update = [&val](int lef, int rig, bool up) {
sgt.updateTree(lef, rig, val); };
function<void(int, int, bool)> query = [&val](int lef, int rig, bool up) {
val = max(val, sgt.queryTree(lef, rig).val); };
for (int i = 1; i <= n; ++i) {
cin >> arr[i]; }
for (int i = 1; i <= n - 1; ++i) {
int x, y; cin >> x >> y;
tree.addEdge(x, y); }
tree.buildHld(1);
for (int i = 1; i <= n; ++i) {
val = arr[i]; tree.applyOnPath(i, i, true, update); }
while (q--) {
int t, x, y; cin >> t >> x >> y;
if (t == 0) {
val = y; tree.applyOnPath(x, x, true, update); }
else {
val = numeric_limits<int> :: min();
tree.applyOnPath(x, y, true, query);
cout << val << "\n"; } }
return 0; }
Emanuel Nrx StarGold2