Heavy-Light

/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 * Date: 2012.10.09
 */

#pragma comment(linker, "/STACK:32000000")

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

const int maxN = (int)1e5;

int m, n, size[maxN], p[maxN];
vector <int> c[maxN];
int tn, root[maxN], num[maxN];
int no[maxN], pos[maxN], *t[maxN];
int mpos, mem[2 * maxN];
int Time, t_in[maxN], t_out[maxN];

void dfs( int v, int pr )
{
  int x;
  t_in[v] = Time++;
  p[v] = pr, size[v] = 1;
  forn(i, c[v].size())
    if ((x = c[v][i]) != pr)
      dfs(x, v), size[v] += size[x];
  t_out[v] = Time++;
}

int new_t( int v )
{
  root[tn] = v;
  return tn++;
}

void build( int v, int v_no )
{
  int x;
  no[v] = v_no, pos[v] = num[v_no]++;
  forn(i, c[v].size())
    if ((x = c[v][i]) != p[v])
      build(x, 2 * size[x] > size[v] ? v_no : new_t(x));
}

void inc( int i, int j, int v )
{
  j += num[i];
  t[i][j] += v;
  for (j /= 2; j; j /= 2)
    t[i][j] = max(t[i][2 * (j)], t[i][2 * (j) + 1]);
}

int get( int i, int l, int r )
{
  int *T = t[i], N = num[i], res = 0;
  for (l += N, r += N; l <= r; l /= 2, r /= 2)
  {
    if (l % 2 == 1) res = max(res, T[l++]);
    if (r % 2 == 0) res = max(res, T[r--]);
  }
  return res;
}

inline bool ancestor( int i, int j )
{
  return t_in[i] <= t_in[j] && t_out[j] <= t_out[i];
}

int main()
{
  int a, b;
  scanf("%d", &n);
  forn(i, n - 1)
  {
    scanf("%d%d", &a, &b), a--, b--;
    c[a].push_back(b), c[b].push_back(a);
  }
  dfs(0, -1);
  build(0, new_t(0));
  forn(i, tn)
    t[i] = mem + mpos, mpos += 2 * num[i];

  scanf("%d", &m);
  while (m--)
  {
    char c;
    scanf(" %c", &c);
    if (c == 'I')
    {
      scanf("%d%d", &a, &b), a--;
      inc(no[a], pos[a], b);
    }
    else
    {
      scanf("%d%d", &a, &b), a--, b--;
      int res = 0;
      forn(t, 2)
      {
        int v;
        while (!ancestor(v = root[no[a]], b))
          res = max(res, get(no[a], 0, pos[a])), a = p[v];
        swap(a, b);
      }
      printf("%d\n", max(res, get(no[a], min(pos[a], pos[b]), max(pos[a], pos[b]))));
    }
  }
  return 0;
}