BZOJ3730 震波 | 动态点分治

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <iostream>

#include <vector>

#define space putchar(' ')

#define enter putchar('\n')

using namespace std;

typedef long long ll;

template <class T>

void read(T &x){

    char c;

    bool op = 0;

    while(c = getchar(), c < '0' || c > '9')

    if(c == '-') op = 1;

    x = c - '0';

    while(c = getchar(), c >= '0' && c <= '9')

    x = x * 10 + c - '0';

    if(op) x = -x;

}

template <class T>

void write(T x){

    if(x < 0) putchar('-'), x = -x;

    if(x >= 10) write(x / 10);

    putchar('0' + x % 10);

}

const int N = 100005, INF = 0x3f3f3f3f;

int n, m, ans;

int ecnt, adj[N], nxt[2*N], go[2*N];

int val[N], fa[N][20], dis[N][20], dep[N], sze[N], son[N], rt, sz;

bool vis[N];

vector <int> bit[N], fbit[N];

/* 变量解释:

fa[i][j]  : 第j次分治中, i所属的连通块的重心

dis[i][j] : i到fa[i][j]的距离

dep[i]    : 点分树上i的深度

sze, son, rt, sz 用于求重心

vis 用于点分治标注

bit[i] : 当i为重心时, 能求"离i距离为j的点的权值和是多少"的树状数组

fbit[i]: 当fa[i][dep[i] - 1]为重心时, 能求"含i连通块离fa[i][dep[i] - 1]距离为j的点的权值和是多少"的树状数组

*/

void add(int u, int v){

    go[++ecnt] = v;

    nxt[ecnt] = adj[u];

    adj[u] = ecnt;

}

void getG(int u, int pre){

    sze[u] = 1, son[u] = 0;

    for(int e = adj[u], v; e; e = nxt[e])

	if(!vis[v = go[e]] && v != pre){

	    getG(v, u);

	    sze[u] += sze[v];

	    son[u] = max(son[u], sze[v]);

	}

    son[u] = max(son[u], sz - sze[u]);

    if(son[u] < son[rt]) rt = u;

}

void dfs(int u, int pre, int top, int d){

    for(int e = adj[u], v; e; e = nxt[e])

	if(!vis[v = go[e]] && v != pre){

	    fa[v][++dep[v]] = top;

	    dis[v][dep[v]] = d;

	    dfs(v, u, top, d + 1);

	}

}

void build(int u){

    vis[u] = 1;

    dfs(u, 0, u, 1);

    int all = sz;

    bit[u].resize(all + 1);

    fbit[u].resize(all + 1);

    for(int e = adj[u], v; e; e = nxt[e])

	if(!vis[v = go[e]]){

	    sz = sze[v] > sze[u] ? all - sze[u] : sze[v];

	    rt = 0;

	    getG(v, u);

	    build(rt);

	}

}

int ask(int u, int k){

    int ret = val[u], lim = bit[u].size() - 1;

    for(k = min(k, lim); k; k -= k & -k) ret += bit[u][k];

    return ret;

}

int fask(int u, int k){

    int ret = 0, lim = fbit[u].size() - 1;

    for(k = min(k, lim); k; k -= k & -k) ret += fbit[u][k];

    return ret;

}

void change(int u, int x){

    int lim = bit[u].size() - 1;

    for(int j = dis[u][dep[u]]; j <= lim && j; j += j & -j) fbit[u][j] += x;

    for(int i = dep[u]; i; i--){

	lim = bit[fa[u][i]].size() - 1;

	for(int j = dis[u][i]; j <= lim; j += j & -j) bit[fa[u][i]][j] += x;

	for(int j = dis[u][i - 1]; j <= lim && j; j += j & -j) fbit[fa[u][i]][j] += x;

    }

}

int query(int u, int k){

    int ret = ask(u, k);

    for(int i = dep[u]; i; i--)

	if(dis[u][i] <= k)

	    ret += ask(fa[u][i], k - dis[u][i]) - fask(fa[u][i + 1], k - dis[u][i]);

    return ret;

}

int main(){

    read(n), read(m);

    for(int i = 1; i <= n; i++) read(val[i]);

    for(int i = 1, u, v; i < n; i++)

	read(u), read(v), add(u, v), add(v, u);

    son[0] = INF, sz = n;

    getG(1, 0);

    build(rt);

    for(int i = 1; i <= n; i++) fa[i][dep[i] + 1] = i;

    for(int i = 1; i <= n; i++) change(i, val[i]);

    int op, x, y;

    while(m--){

	read(op), read(x), read(y);

	x ^= ans, y ^= ans;

	//printf("op = %d, x = %d, y = %d\n", op, x, y);

	if(op == 0) write(ans = query(x, y)), enter;

	else change(x, y - val[x]), val[x] = y;

    }

    return 0;

}