BZOJ3730 震波

#include <cstdio>
#include <cstring>

#include <algorithm>

#define LOG(FMT...) // fprintf(stderr, FMT)

struct fenwick {
    int n;
    int* fw;

    void set(int n);
    void change(int k, int x);
    int query(int k) const;
};

struct edge {
    int v;
    edge* next;
};

const int N = 100010, LGN = 20;

int n, ql, qr;
int val[N], q[N], sum[N], maxsum[N], divcnt[N], prt[N], dep[N], maxdep[N];
int divrt[N][LGN], divsprt[N][LGN], divdep[N][LGN];
fenwick divfw[N][LGN];
bool cut[N], vis[N];
edge* g[N];

int low_bit(int x);
void add_edge(int u, int v);
void divide(int u);
void bfs(int u);

int main() {
//  freopen("test.err", "w", stderr);
    int m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &val[i]);
    for (int rep = 1; rep < n; ++rep) {
        int u, v;
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
    divide(1);
    int last = 0;
    while (m--) {
        int op, u, x;
        scanf("%d%d%d", &op, &u, &x);
        u ^= last;
        x ^= last;
        if (op == 0) {
            last = 0;
            for (int i = 0; i < divcnt[u] - 1; ++i) {
                if (divdep[u][i] > x)
                    continue;
                last += val[divrt[u][i]];
                last += divfw[divrt[u][i]][i].query(x - divdep[u][i]);
                last -= divfw[divsprt[u][i]][i].query(x - divdep[u][i]);
            }
            last += val[u];
            last += divfw[u][divcnt[u] - 1].query(x);
            printf("%d\n", last);
        } else {
            int delt = x - val[u];
            val[u] = x;
            for (int i = 0; i < divcnt[u] - 1; ++i) {
                divfw[divrt[u][i]][i].change(divdep[u][i], delt);
                divfw[divsprt[u][i]][i].change(divdep[u][i], delt);
            }
        }
    }
    return 0;
}

void bfs(int u) {
    ql = 0;
    qr = 1;
    q[0] = u;
    while (ql < qr) {
        u = q[ql++];
        vis[u] = true;
        for (edge* p = g[u]; p; p = p->next)
            if (!vis[p->v] && !cut[p->v]) {
                q[qr++] = p->v;
            }
    }
}

void divide(int u) {
    bfs(u);
    int div = q[qr - 1];
    for (int i = qr - 1; i >= 0; --i) {
        u = q[i];
        vis[u] = false;
        sum[u] = 1;
        maxsum[u] = 0;
        for (edge* p = g[u]; p; p = p->next)
            if (!vis[p->v] && !cut[p->v]) {
                sum[u] += sum[p->v];
                maxsum[u] = std::max(maxsum[u], sum[p->v]);
            }
        maxsum[u] = std::max(maxsum[u], qr - sum[u]);
        if (maxsum[u] < maxsum[div])
            div = u;
    }
    cut[div] = true;
    bfs(div);
    LOG("DIV %d\n", div);
    int cd = divcnt[div];
    ++divcnt[div];
    if (cd > 18) {
        LOG("ERR\n");
    }
    vis[div] = false;
    divrt[div][cd] = div;
    for (edge* p = g[div]; p; p = p->next)
        if (!cut[p->v]) {
            divdep[p->v][cd] = 1;
            divsprt[p->v][cd] = p->v;
        }
    for (int i = 1; i < qr; ++i) {
        u = q[i];
        ++divcnt[u];
        vis[u] = false;
        divrt[u][cd] = div;
        maxdep[divsprt[u][cd]] = divdep[u][cd];
        for (edge* p = g[u]; p; p = p->next)
            if (!cut[p->v] && vis[p->v]) {
                divsprt[p->v][cd] = divsprt[u][cd];
                divdep[p->v][cd] = divdep[u][cd] + 1;
            }
    }
    divfw[div][cd].set(divdep[q[qr - 1]][cd]);
    for (int i = 1; i < qr; ++i) {
        u = q[i];
        if (divdep[u][cd] == 1) {
            LOG("%d SET %d\n", u, maxdep[u]);
            divfw[u][cd].set(maxdep[u]);
        }
        divfw[div][cd].change(divdep[u][cd], val[u]);
        divfw[divsprt[u][cd]][cd].change(divdep[u][cd], val[u]);
    }
    for (edge* p = g[div]; p; p = p->next) {
        if (!cut[p->v])
            divide(p->v);
    }
}

void add_edge(int u, int v) {
    static edge pool[N * 2];
    static edge* p = pool;
    p->v = v;
    p->next = g[u];
    g[u] = p;
    ++p;
}

void fenwick::set(int n) {
    static int pool[N * LGN * 2];
    static int* top = pool;
//  if (top - pool > N * LGN)
//      LOG("SET %ld %d\n", top - pool, N * LGN * 2);
    fenwick::n = n;
    fw = top - 1;
    top += n;
}

void fenwick::change(int k, int x) {
    for (; k <= n; k += low_bit(k))
        fw[k] += x;
}

int fenwick::query(int k) const {
    int ret = 0;
    if (k > n)
        k = n;
    for (; k; k -= low_bit(k)) {
        ret += fw[k];
    }
    return ret;
}

int low_bit(int x) {
    return x & -x;
}