SHOW:
|
|
- or go back to the newest paste.
| 1 | /** | |
| 2 | * Author: Sergey Kopeliovich ([email protected]) | |
| 3 | * Date: 2012.10.09 | |
| 4 | */ | |
| 5 | ||
| 6 | #pragma comment(linker, "/STACK:32000000") | |
| 7 | ||
| 8 | #include <cstdio> | |
| 9 | #include <algorithm> | |
| 10 | #include <vector> | |
| 11 | ||
| 12 | using namespace std; | |
| 13 | ||
| 14 | #define forn(i, n) for (int i = 0; i < (int)(n); i++) | |
| 15 | ||
| 16 | const int maxN = (int)1e5; | |
| 17 | ||
| 18 | int m, n, size[maxN], p[maxN]; | |
| 19 | vector <int> c[maxN]; | |
| 20 | int tn, root[maxN], num[maxN]; | |
| 21 | int no[maxN], pos[maxN], *t[maxN]; | |
| 22 | int mpos, mem[2 * maxN]; | |
| 23 | int Time, t_in[maxN], t_out[maxN]; | |
| 24 | ||
| 25 | void dfs( int v, int pr ) | |
| 26 | {
| |
| 27 | int x; | |
| 28 | t_in[v] = Time++; | |
| 29 | p[v] = pr, size[v] = 1; | |
| 30 | forn(i, c[v].size()) | |
| 31 | if ((x = c[v][i]) != pr) | |
| 32 | dfs(x, v), size[v] += size[x]; | |
| 33 | t_out[v] = Time++; | |
| 34 | } | |
| 35 | ||
| 36 | int new_t( int v ) | |
| 37 | {
| |
| 38 | root[tn] = v; | |
| 39 | return tn++; | |
| 40 | } | |
| 41 | ||
| 42 | void build( int v, int v_no ) | |
| 43 | {
| |
| 44 | int x; | |
| 45 | no[v] = v_no, pos[v] = num[v_no]++; | |
| 46 | forn(i, c[v].size()) | |
| 47 | if ((x = c[v][i]) != p[v]) | |
| 48 | build(x, 2 * size[x] > size[v] ? v_no : new_t(x)); | |
| 49 | } | |
| 50 | ||
| 51 | void inc( int i, int j, int v ) | |
| 52 | {
| |
| 53 | j += num[i]; | |
| 54 | t[i][j] += v; | |
| 55 | for (j /= 2; j; j /= 2) | |
| 56 | t[i][j] = max(t[i][2 * (j)], t[i][2 * (j) + 1]); | |
| 57 | } | |
| 58 | ||
| 59 | int get( int i, int l, int r ) | |
| 60 | {
| |
| 61 | int *T = t[i], N = num[i], res = 0; | |
| 62 | for (l += N, r += N; l <= r; l /= 2, r /= 2) | |
| 63 | {
| |
| 64 | if (l % 2 == 1) res = max(res, T[l++]); | |
| 65 | if (r % 2 == 0) res = max(res, T[r--]); | |
| 66 | } | |
| 67 | return res; | |
| 68 | } | |
| 69 | ||
| 70 | inline bool ancestor( int i, int j ) | |
| 71 | {
| |
| 72 | return t_in[i] <= t_in[j] && t_out[j] <= t_out[i]; | |
| 73 | } | |
| 74 | ||
| 75 | int main() | |
| 76 | {
| |
| 77 | int a, b; | |
| 78 | scanf("%d", &n);
| |
| 79 | forn(i, n - 1) | |
| 80 | {
| |
| 81 | scanf("%d%d", &a, &b), a--, b--;
| |
| 82 | c[a].push_back(b), c[b].push_back(a); | |
| 83 | } | |
| 84 | dfs(0, -1); | |
| 85 | build(0, new_t(0)); | |
| 86 | forn(i, tn) | |
| 87 | t[i] = mem + mpos, mpos += 2 * num[i]; | |
| 88 | ||
| 89 | scanf("%d", &m);
| |
| 90 | while (m--) | |
| 91 | {
| |
| 92 | char c; | |
| 93 | scanf(" %c", &c);
| |
| 94 | if (c == 'I') | |
| 95 | {
| |
| 96 | scanf("%d%d", &a, &b), a--;
| |
| 97 | inc(no[a], pos[a], b); | |
| 98 | } | |
| 99 | else | |
| 100 | {
| |
| 101 | scanf("%d%d", &a, &b), a--, b--;
| |
| 102 | int res = 0; | |
| 103 | forn(t, 2) | |
| 104 | {
| |
| 105 | int v; | |
| 106 | while (!ancestor(v = root[no[a]], b)) | |
| 107 | res = max(res, get(no[a], 0, pos[a])), a = p[v]; | |
| 108 | swap(a, b); | |
| 109 | } | |
| 110 | printf("%d\n", max(res, get(no[a], min(pos[a], pos[b]), max(pos[a], pos[b]))));
| |
| 111 | } | |
| 112 | } | |
| 113 | return 0; | |
| 114 | } |
