Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <signal.h>
- #include <stdio.h>
- #include <unistd.h>
- #include <cstring>
- #define pb push_back
- using namespace std;
- const int N = 50001;
- vector<int> g[N], lca[N];
- vector<vector<int> > hld;
- int tin[N], tout[N], sz[N], val[N];
- pair<int,int> inds[N];
- int n, m;
- int timer = 0;
- int l = 1;
- void dfs_hld(int v, int vec=0, int p=0) {
- hld[vec].push_back(v);
- if (g[v].size() == 1 && v != 0 || n == 1) {
- return;
- }
- int maxi = -1;
- for (int i = 0; i < g[v].size(); ++i) {
- if (g[v][i] != p && (sz[g[v][i]] > sz[g[v][maxi]] || maxi == -1))
- maxi = i;
- }
- for (int i = 0; i < g[v].size(); ++i) {
- if (g[v][i] == p) continue;
- if (i == maxi) {
- dfs_hld(g[v][i], vec, v);
- }
- else {
- hld.push_back(vector<int>());
- dfs_hld(g[v][i], hld.size()-1, v);
- }
- }
- }
- int dfs(int v, int p=0) {
- lca[v][0] = p;
- tin[v] = timer++;
- sz[v] = 1;
- for (int i = 1; i <= l; ++i) {
- lca[v][i] = lca[lca[v][i-1]][i-1];
- }
- for (int to : g[v]) {
- if (to != p)
- sz[v] += dfs(to, v);
- }
- tout[v] = timer++;
- return sz[v];
- }
- bool isparent(int v, int u) {
- return tin[v] <= tin[u] && tout[v] >= tout[u];
- }
- int get_lca(int v, int u) {
- if (isparent(v, u)) return v;
- if (isparent(u, v)) return u;
- for (int i = l; i --> 0;) {
- // cout << lca[v][i] << endl;
- if (!isparent(lca[v][i], u))
- v = lca[v][i];
- }
- return lca[v][0];
- }
- void init() {
- while ((1<<l) <= n) ++l;
- for (int i = 0; i < n; ++i) {
- lca[i] = vector<int>(l+1);
- }
- }
- class ST {
- private:
- vector<int> a, t;
- int n;
- public:
- ST(){}
- ST(vector<int> v) : a(v) {
- n = v.size();
- t.assign(4*n+10, 0);
- build(1, 0, n-1);
- }
- void build(int v, int tl, int tr) {
- if (tl == tr)
- t[v] = a[tl];
- else {
- int tm = (tl + tr) >> 1;
- build(v*2, tl, tm);
- build(v*2+1, tm+1, tr);
- t[v] = max(t[v*2], t[v*2+1]);
- }
- }
- int get_max(int v, int tl, int tr, int l, int r) {
- if (l > r)
- return -1;
- if (tl == l && tr == r)
- return t[v];
- int tm = (tl + tr) >> 1;
- return max(get_max(v*2, tl, tm, l, min(r, tm)),
- get_max(v*2+1, tm+1, tr, max(l, tm+1), r));
- }
- void modify(int v, int tl, int tr, int pos, int val) {
- if (tl == tr)
- t[v] = val;
- else {
- int tm = (tl + tr) >> 1;
- if (pos <= tm)
- modify(v*2, tl, tm, pos, val);
- else
- modify(v*2+1, tm+1, tr, pos, val);
- t[v] = max(t[v*2], t[v*2+1]);
- }
- }
- int get_size() {
- return n;
- }
- };
- vector<ST*> forest;
- int get_ans(int a, int b) {
- int p = get_lca(a, b);
- // solve for [a, p]
- int pind = inds[p].first;
- int amax = -1, bmax = -1;
- while (inds[a].first != pind) {
- amax = max(amax, forest[inds[a].first]->get_max(
- 1, 0, forest[inds[a].first]->get_size()-1, 0, inds[a].second));
- a = lca[hld[inds[a].first][0]][0];
- }
- amax = max(amax, forest[inds[a].first]->get_max(
- 1, 0, forest[inds[a].first]->get_size()-1, inds[p].second, inds[a].second));
- // solve for [b, p]
- while (inds[b].first != pind) {
- bmax = max(bmax, forest[inds[b].first]->get_max(
- 1, 0, forest[inds[b].first]->get_size()-1, 0, inds[b].second));
- b = lca[hld[inds[b].first][0]][0];
- }
- bmax = max(bmax, forest[inds[b].first]->get_max(
- 1, 0, forest[inds[b].first]->get_size()-1, inds[p].second, inds[b].second));
- int ans = max(amax, bmax);
- return ans;
- }
- void update(int v, int val) {
- forest[inds[v].first]->modify(1, 0, forest[inds[v].first]->get_size()-1, inds[v].second, val);
- }
- void segfault_sigaction(int signal, siginfo_t *si, void *arg) {
- while (1) {};
- }
- int32_t main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- struct sigaction sa;
- memset(&sa, 0, sizeof(struct sigaction));
- sigemptyset(&sa.sa_mask);
- sa.sa_sigaction = segfault_sigaction;
- sa.sa_flags = SA_SIGINFO;
- sigaction(SIGSEGV, &sa, NULL);
- cin >> n;
- for (int i = 0; i < n; ++i) {
- cin >> val[i];
- }
- for (int i = 0; i < n-1; ++i) {
- int a, b;
- cin >> a >> b;
- --a, --b;
- g[a].pb(b);
- g[b].pb(a);
- }
- init();
- dfs(0);
- hld.push_back(vector<int>());
- try {
- dfs_hld(0);
- } catch(...) {while(1){}}
- for (int i = 0; i < hld.size(); ++i) {
- vector<int> vev;
- for (int j = 0; j < hld[i].size(); ++j) {
- vev.push_back(val[hld[i][j]]);
- }
- forest.push_back(new ST(vev));
- for (int j = 0; j < hld[i].size(); ++j) {
- int p = hld[i][j];
- inds[p] = {i, j};
- // cout << p << " ";
- }
- // cout << endl;
- }
- int q;
- cin >> q;
- for (int i = 0; i < q; ++i) {
- char c;
- cin >> c;
- int a, b;
- cin >> a >> b;
- if (c == '?') {
- --a, --b;
- cout << get_ans(a, b) << endl;
- }
- else {
- --a;
- update(a, b);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement