记录编号	318112	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上操作	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	1.229 s
提交时间	2016-10-08 21:03:20	内存使用	114.85 MiB

#include "stdio.h"
#include "stdlib.h"
typedef long long LL;
 
const int maxnumber = 1001000;
struct Edge
{
	int to, next;
}edges[maxnumber << 1];
int head[maxnumber], tot;
int n, m;
LL value[maxnumber], num;
int depth[maxnumber], size[maxnumber], fa[maxnumber], son[maxnumber];
int dfn[maxnumber], id[maxnumber], top[maxnumber], dfsclock;
LL tree[maxnumber << 2], lazy[maxnumber << 2];
 
template <class T> inline void Read(T& a)
{
	a = 0;
	int minus = 1;
	char ch = getchar();
	if(ch == '-') minus = -1;
	while(ch < '0' || ch > '9'){
		ch = getchar();
		if(ch == '-') minus = -1;
	}
	while(ch >= '0' && ch <= '9'){
		a = a * 10 + ch - '0';
		ch = getchar();
	}
	a = a * minus;
}
 
template <class T> inline void Write(T a)
{
	int cnt = 0;
	if(a < 0){
		putchar('-');
		a = -a;
	}
	char ch[50] = {'\0'};
	while(1){
		ch[++cnt] = a % 10 + '0';
		a /= 10;
		if(!a) break;
	}
	while(cnt)
		putchar(ch[cnt--]);
	puts("");
}
 
template <class T> inline void Swap(T& a, T& b)
{
	T tmp = a;
	a = b;
	b = tmp;
}
 
inline void AddEdge(const int& from, const int& to)
{
	edges[++tot].to = to;
	edges[tot].next = head[from];
	head[from] = tot;
}
 
void Segment_Tree_Build(const int& l, const int& r, const int& rt)
{
	// printf("l:%d r:%d rt:%d\n", l, r, rt); while(1);
	if(l == r){
		tree[rt] = value[id[l]];
		return;
	}
	const int mid = (l + r) >> 1, lch = rt << 1, rch = lch | 1;
	Segment_Tree_Build(l, mid, lch);
	Segment_Tree_Build(mid+1, r, rch);
	tree[rt] = tree[lch] + tree[rch];
}
 
inline void PushDown(const int l, const int r, const int& rt)
{
	const int mid = (l + r) >> 1,lch = rt << 1, rch = lch | 1;
	lazy[lch] += lazy[rt]; lazy[rch] += lazy[rt];
	tree[lch] += (LL)(mid - l + 1) * lazy[rt];
	tree[rch] += (LL)(r - mid) * lazy[rt];
	lazy[rt] = 0;
}
 
void Segment_Tree_Add(const int& l, const int& r, const int& rt, const int& s, const int& t)
{
	if(s <= l && t >= r){
		tree[rt] += (r - l + 1) * num;
		lazy[rt] += num;
		return;
	}
	if(lazy[rt]) PushDown(l, r, rt);
	const int mid = (l + r) >> 1, lch = rt << 1, rch = lch | 1;
	if(t <= mid) Segment_Tree_Add(l, mid, lch, s, t);
	else if(s >= mid + 1) Segment_Tree_Add(mid+1, r, rch, s, t);
	else{
		Segment_Tree_Add(l, mid, lch, s, mid);
		Segment_Tree_Add(mid+1, r, rch, mid+1, t);
	}
	tree[rt] = tree[lch] + tree[rch];
}
 
LL Segment_Tree_Sum(const int& l, const int& r, const int& rt, const int& s, const int& t)
{
	if(s <= l && t >= r) return tree[rt];
	if(lazy[rt]) PushDown(l, r, rt);
	const int mid = (l + r) >> 1, lch = rt << 1, rch = lch | 1;
	if(t <= mid) return Segment_Tree_Sum(l, mid, lch, s, t);
	else if(s >= mid + 1) return Segment_Tree_Sum(mid+1, r, rch, s, t);
	return Segment_Tree_Sum(l, mid, lch, s, mid) + Segment_Tree_Sum(mid+1, r, rch, mid+1, t);
}
 
void DFS1(const int& a)
{
	size[a] = 1;
	for(int i = head[a]; i; i = edges[i].next){
		int to = edges[i].to;
		if(to == fa[a]) continue;
		depth[to] = depth[a] + 1;
		fa[to] = a;
		DFS1(to);
		size[a] += size[to];
		if(size[to] > size[son[a]]) son[a] = to;
	}
}
 
void DFS2(const int& a, const int& tp)
{
	dfn[a] = ++dfsclock;
	id[dfsclock] = a;
	top[a] = tp;
	if(son[a]) DFS2(son[a], tp);
	for(int i = head[a]; i; i = edges[i].next){
		int to = edges[i].to;
		if(to == fa[a] || to == son[a]) continue;
		DFS2(to, to);
	}
}
 
inline LL Query(int s, int t)
{
	LL ret = 0;
	int f1 = top[s], f2 = top[t];
	while(f1 != f2){
		if(depth[f1] < depth[f2]){
			Swap(f1, f2);
			Swap(s, t);
		}
		ret += Segment_Tree_Sum(1, n, 1, dfn[f1], dfn[s]);
		s = fa[f1];
		f1 = top[s];
	}
	if(depth[s] < depth[t]) Swap(s, t);
	ret += Segment_Tree_Sum(1, n, 1, dfn[t], dfn[s]);
	return ret;
}
 
#define SUBMIT
int main(int argc, char const *argv[])
{
#ifdef SUBMIT
	freopen("haoi2015_t2.in", "r", stdin); freopen("haoi2015_t2.out", "w", stdout);
#endif
 
	int from, to, order, s;
	Read(n); Read(m);
	for(int i = 1; i <= n; i++) Read(value[i]);
	for(int i = 1; i < n; i++){
		Read(from); Read(to);
		AddEdge(from, to);
		AddEdge(to, from);
	}
 
	depth[1] = 1;
	DFS1(1);
	DFS2(1, 1);
	Segment_Tree_Build(1, n, 1);
 
	for(int i = 1; i <= m; i++){
		Read(order);
		if(order == 1){
			Read(s); Read(num);
			Segment_Tree_Add(1, n, 1, dfn[s], dfn[s]);
		}
		else if(order == 2){
			Read(s); Read(num);
			Segment_Tree_Add(1, n, 1, dfn[s], dfn[s] + size[s] - 1);
		}
		else{
			Read(s);
			Write(Query(s, 1));
		}
	}
 
#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);
#endif
 
	return 0;
}