记录编号	246031	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上操作	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	2.003 s
提交时间	2016-04-04 20:53:33	内存使用	10.89 MiB

//KZNS
#include <fstream>
#include <vector>
using namespace std;
//
ifstream fin ("haoi2015_t2.in");
ofstream fout ("haoi2015_t2.out");
const int Nmax = 100003;
class poi {
public:
	int l, r;
	long long sm, ad;
};
//
int N, M;
int pv[Nmax] = {0};
vector<int> gp[Nmax];
int fa[Nmax] = {0};
int ddp[Nmax] = {0};
int cts[Nmax] = {0};
int hc[Nmax] = {0};
int dtp[Nmax] = {0};
int dtm[Nmax] = {0};
int dff[Nmax] = {0};
int ttmm = 0;
poi tr[262144];
int tv[Nmax] = {0};
//
void rin() {
	fin >> N >> M;
	for (int i = 1; i <= N; i++)
		fin >> pv[i];
	int a, b;
	for (int i = 1; i < N; i++) {
		fin >> a >> b;
		gp[a].push_back(b);
		gp[b].push_back(a);
	}
}
void DFS1(int x, int f) {
	cts[x] = 1;
	fa[x] = f;
	ddp[x] = ddp[f] + 1;
	for (int i = 0; i < gp[x].size(); i++) {
		if (!cts[gp[x][i]]) {
			DFS1(gp[x][i], x);
			cts[x] += cts[gp[x][i]];
			if (cts[hc[x]] < cts[gp[x][i]])
				hc[x] = gp[x][i];
		}
	}
}
void DFS2(int x, int tp) {
	dff[x] = dtm[x] = ++ttmm;
	dtp[x] = tp;
	if (hc[x]) {
		DFS2(hc[x], tp);
		dff[x] = max(dff[x], dff[hc[x]]);
	}
	for (int i = 0; i < gp[x].size(); i++) {
		if (!dtm[gp[x][i]]) {
			DFS2(gp[x][i], gp[x][i]);
			dff[x] = max(dff[x], dff[gp[x][i]]);
		}
	}
}
void vtt() {
	for (int i = 1; i <= N; i++)
		tv[dtm[i]] = pv[i];
}
inline void updata(int x);
inline void downdata(int x);
void maketree(int x, int l, int r) {
	poi &u = tr[x];
	u.l = l;
	u.r = r;
	u. ad = 0;
	if (l == r) {
		u.sm = tv[r];
	}
	else {
		maketree(x<<1, l, l+r>>1);
		maketree(x<<1^1, (l+r>>1)+1, r);
		updata(x);
	}
}
void tad(int x, int l, int r, long long c) {
	poi &u = tr[x];
	if (l <= u.l && u.r <= r) {
		u.ad += c;
		u.sm += c*(u.r-u.l+1);
	}
	else {
		downdata(x);
		if (l <= tr[x<<1].r)
			tad(x<<1, l, r, c);
		if (tr[x<<1^1].l <= r)
			tad(x<<1^1, l, r, c);
		updata(x);
	}
}
long long Qin(int x, int l, int r) {
	poi &u = tr[x];
	if (l <= u.l && u.r <= r) {
		return u.sm;
	}
	else {
		long long sm = 0;
		downdata(x);
		if (l <= tr[x<<1].r)
			sm += Qin(x<<1, l, r);
		if (tr[x<<1^1].l <= r)
			sm += Qin(x<<1^1, l, r);
		return sm;
	}
}
//
int main() {
	rin();
	DFS1(1, 0);
	DFS2(1, 1);
	vtt();
	maketree(1, 1, N);
	int t, x, a;
	for (int i = 0; i < M; i++) {
		fin >> t;
		if (t == 1) {
			fin >> x >> a;
			tad(1, dtm[x], dtm[x], a);
		}
		else if (t == 2) {
			fin >> x >> a;
			tad(1, dtm[x], dff[x], a);
		}
		else if (t == 3) {
			fin >> x;
			long long sm = 0;
			while (true) {
				if (dtp[x] == 1) {
					sm += Qin(1, 1, dtm[x]);
					break;
				}
				else {
					sm +=Qin(1, dtm[dtp[x]], dtm[x]);
					x = fa[dtp[x]];
				}
			}
			fout << sm << endl;
		}
	}
	return 0;
}
//
inline void updata(int x) {
	tr[x].sm = tr[x<<1].sm + tr[x<<1^1].sm;
}
inline void downdata(int x) {
	if (tr[x].ad) {
		tad(x<<1, tr[x].l, tr[x].r, tr[x].ad);
		tad(x<<1^1, tr[x].l, tr[x].r, tr[x].ad);
		tr[x].ad = 0;
	}
}
//UBWH