HDU Aragorn's Story

题目链接

树抛入门裸题，这题是区间改动单点查询，于是套树状数组就OK了

代码：

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

using namespace std;

const int N = 50005;

inline int lowbit(int x) {return x&(-x);}

int dep[N], fa[N], son[N], sz[N], top[N], id[N], idx;

vector<int> g[N];

int bit[N];

int n, m, p, val[N];

void dfs1(int u, int f, int d) {

	dep[u] = d;

	sz[u] = 1;

	fa[u] = f;

	son[u] = 0;

	for (int i = 0; i < g[u].size(); i++) {

		int v = g[u][i];

		if (v == f) continue;

		dfs1(v, u, d + 1);

		sz[u] += sz[v];

		if (sz[son[u]] < sz[v])

			son[u] = v;

	}

}

void dfs2(int u, int tp) {

	id[u] = ++idx;

	top[u] = tp;

	if (son[u]) dfs2(son[u], tp);

	for (int i = 0; i < g[u].size(); i++) {

		int v = g[u][i];

		if (v == fa[u] || v == son[u]) continue;

		dfs2(v, v);

	}

}

void add(int x, int v) {

	while (x < N) {

		bit[x] += v;

		x += lowbit(x);

	}

}

void add(int l, int r, int v) {

	add(l, v);

	add(r + 1, -v);

}

void gao(int u, int v, int w) {

	int tp1 = top[u], tp2 = top[v];

	while (tp1 != tp2) {

		if (dep[tp1] < dep[tp2]) {

			swap(tp1, tp2);

			swap(u, v);

		}

		add(id[tp1], id[u], w);

		u = fa[tp1];

		tp1 = top[u];

	}

	if (dep[u] > dep[v]) swap(u, v);

	add(id[u], id[v], w);

}

int query(int x) {

	int ans = 0;

	while (x) {

		ans += bit[x];

		x -= lowbit(x);

	}

	return ans;

}

int main() {

	while (~scanf("%d%d%d", &n, &m, &p)) {

		idx = 0;

		memset(bit, 0, sizeof(bit));

		for (int i = 1; i <= n; i++) {

			scanf("%d", &val[i]);

			g[i].clear();

		}

		int u, v;

		while (m--) {

			scanf("%d%d", &u, &v);

			g[u].push_back(v);

			g[v].push_back(u);

		}

		dfs1(1, -1, 1);

		dfs2(1, 1);

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

		char q[2];

		int a, b, c;

		while (p--) {

			scanf("%s", q);

			if (q[0] == 'I' || q[0] == 'D') {

				scanf("%d%d%d", &a, &b, &c);

				if (q[0] == 'D') c = -c;

				gao(a, b, c);

			} else {

				scanf("%d", &a);

				printf("%d\n", query(id[a]));

			}

		}

	}

	return 0;

}