不知道为什么MLE#2

#include <bits/stdc++.h>
#define _ 500005
typedef unsigned long long ull;
using namespace std;

int n, m, q;
int a[_];
vector <int> t[_];
const ull k = 131313131;
ull hsh[_], p[_];
unordered_map <ull, int> rfl; 

struct BIT
{
  ull tr[_];
  inline int lb(int x) { return x & (-x); }
  void add(int x, ull v) {
    for (; x <= m; v *= p[lb(x)], x += lb(x)) tr[x] += v;
  }
  ull ask(int x) {
    ull sum(0), base(1);
    for (; x; base *= p[lb(x)], x -= lb(x)) sum += tr[x] * base; 
    return sum;
  }
} Tree;
void init()
{
  p[0] = 1;
  for (int i(1); i <= m; i ++) p[i] = p[i - 1] * k;
}
void dfs(int u)
{
  int l = t[u].size();
  for (int i(0); i < l; i ++) {
    int v = t[u][i];
    hsh[v] = hsh[u] * k + (i + 1);
    rfl[hsh[v]] = v;
    dfs(v);
  }
}
int solve(int u, int l, int r)
{
  int L(l), R(r);
  ull w(0);
  while (L <= R) {
    int mid (L + R >> 1);
    ull fr = hsh[u], tl = Tree.ask(mid) - Tree.ask(l - 1)*p[(mid - l + 1)];
    if (rfl[fr * p[(mid - l + 1)] + tl]) {
      L = mid + 1, w = fr * p[(mid - l + 1)] + tl;
    } else {
      R = mid - 1;
    }
  } return (w ? rfl[w] : u);
}
int main()
{
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin >> n >> m >> q;
  for (int i(1); i <= n; i ++) {
    int fa; cin >> fa;
    t[fa].push_back(i);
  }
  for (int i(1); i <= n; i ++)
    sort(t[i].begin(), t[i].end());
  init(); dfs(0); 
  for (int i(1); i <= m; i ++) {
    cin >> a[i];
    Tree.add(i, a[i]);
  }
  for (int i(1); i <= q; i ++) {
    int op, x, l, r, t, nv;
    cin >> op;
    if (op == 1) {
      cin >> x >> l >> r;
      printf ("%d\n", solve(x, l, r));
    } else {
      cin >> t >> nv;
      Tree.add(t, nv - a[t]); a[t] = nv;
    }
  }
  return 0;
}
/*
6 6 10
0 1 2 2 1 5
1 2 2 1 2 1
1 1 1 3
1 5 2 6
1 6 5 6
1 2 3 5
1 2 4 4
2 2 1
1 1 1 6
1 1 2 4
2 1 2
1 1 1 5

4
5
6
4
3
3
4
6
*/