Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<vector>
- #include<algorithm>
- #include<cstdio>
- #include<cassert>
- using namespace std;
- vector<int>g[100007];
- int parent[100007][22];
- int sz[100007];
- bool used[100007];
- int block[100007], blockpos[100007];
- int tin[100007], tout[100007], h[100007];
- int timer = 1;
- void dfs(int v, int p = 1, int curh = 1)
- {
- used[v] = true;
- parent[v][0] = p;
- sz[v] = 1;
- h[v] = curh;
- tin[v] = timer;
- timer++;
- for (int j = 1; j < 22; j++)
- {
- parent[v][j] = parent[parent[v][j - 1]][j - 1];
- }
- for (int i = 0; i < g[v].size(); i++)
- {
- int to = g[v][i];
- if (!used[to])
- {
- dfs(to, v, curh + 1);
- sz[v] += sz[to];
- }
- }
- tout[v] = timer;
- timer++;
- }
- bool isHeavy(int u, int v)
- {
- if (sz[u] > sz[v]) swap(u, v);
- return 2 * sz[u] > sz[v];
- }
- bool isAncestor(int u, int v)
- {
- return tin[u] < tin[v] && tout[u] > tout[v];
- }
- struct segment_tree
- {
- vector<long long>tree;
- void init(int n)
- {
- tree.resize(4 * n + 2);
- }
- void add(int v, int tl, int tr, int pos, int val)
- {
- if (tl == tr)
- {
- tree[v] += val;
- }
- else
- {
- int tm = (tl + tr) / 2;
- if (pos <= tm)
- {
- add(2 * v, tl, tm, pos, val);
- }
- else
- {
- add(2 * v + 1, tm + 1, tr, pos, val);
- }
- tree[v] = max(tree[2 * v], tree[2 * v + 1]);
- }
- }
- long long getMax(int v, int tl, int tr, int l, int r)
- {
- if (r<tl || l>tr) return 0;
- if (tl >= l && tr <= r) return tree[v];
- int tm = (tl + tr) / 2;
- return max(getMax(2 * v, tl, tm, l, r), getMax(2 * v + 1, tm + 1, tr, l, r));
- }
- };
- struct hldBlock
- {
- segment_tree st;
- int downv, upv, size;
- void init(int _downv, int _upv, int _size)
- {
- downv = _downv;
- upv = _upv;
- size = _size;
- st.init(size + 1);
- }
- long long get(int u, int v)
- {
- if (isAncestor(u, upv) || isAncestor(downv, v))
- {
- return 0;
- }
- int l = downv, r = upv;
- if (isAncestor(u, downv))
- {
- l = u;
- }
- if (isAncestor(upv, v))
- {
- r = v;
- }
- return st.getMax(1, 1, size, blockpos[l], blockpos[r]);
- }
- void change(int v, int val)
- {
- st.add(1, 1, size, blockpos[v], val);
- }
- };
- hldBlock blocks[100007];
- void buildDecomposition(int n)
- {
- dfs(1);
- int bcnt = 1;
- for (int i = 1; i <= n; i++)
- {
- bool hasHeavy = false;
- for (int j = 0; j < g[i].size(); j++)
- {
- int to = g[i][j];
- if (to == parent[i][0]) continue;
- if (isHeavy(i, to)) hasHeavy = true;
- }
- if (!hasHeavy)
- {
- vector<int>cur;
- int j = i;
- while (j != 1 && isHeavy(j, parent[j][0]))
- {
- assert(block[j] == 0);
- cur.push_back(j);
- j = parent[j][0];
- }
- if (cur.size() == 0 || isHeavy(cur.back(), j))
- {
- assert(block[j] == 0);
- cur.push_back(j);
- }
- blocks[bcnt].init(cur[0], cur.back(), cur.size() + 1);
- for (int i = 0; i < cur.size(); i++)
- {
- int cv = cur[i];
- block[cv] = bcnt;
- blockpos[cv] = i + 1;
- }
- bcnt++;
- }
- }
- }
- int getLca(int u, int v)
- {
- if (isAncestor(u, v)) return u;
- if (isAncestor(v, u)) return v;
- if (u == v) return u;
- for (int i = 20; i >= 0; i--)
- {
- if (!isAncestor(parent[u][i], v))
- {
- u = parent[u][i];
- }
- }
- return parent[u][0];
- }
- long long solvePath(int u, int v)
- {
- int curb = block[u];
- long long ans = 0;
- while (1)
- {
- ans = max(ans, blocks[curb].get(u, v));
- if (blocks[curb].upv == 1) break;
- curb = block[parent[blocks[curb].upv][0]];
- }
- return ans;
- }
- long long getMax(int u, int v)
- {
- int lca = getLca(u, v);
- return max(solvePath(u, lca), solvePath(v, lca));
- }
- void change(int v, int val)
- {
- blocks[block[v]].change(v, val);
- }
- int main()
- {
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- int n;
- scanf("%d\n", &n);
- for (int i = 1; i < n; i++)
- {
- int u, v;
- scanf("%d %d\n", &u, &v);
- g[u].push_back(v);
- g[v].push_back(u);
- }
- buildDecomposition(n);
- for (int i = 1; i <= n; i++)
- {
- assert(block[i] != 0);
- }
- int q;
- scanf("%d\n", &q);
- for (int i = 1; i <= q; i++)
- {
- char mode;
- scanf("%c ", &mode);
- if (mode == 'I')
- {
- int pos, val;
- scanf("%d %d\n", &pos, &val);
- change(pos, val);
- }
- else
- {
- int u, v;
- scanf("%d %d\n", &u, &v);
- printf("%lld\n", getMax(u, v));
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement