HYSBZ 4034 T2

Description

 有一棵點數為 N 的樹，以點 1 為根，且樹點有邊權。然後有 M 個

操作，分為三種： 操作 1 ：把某個節點 x 的點權增加 a 。 操作 2 ：把某個節點 x 為根的子樹中所有點的點權都增加 a 。 操作 3 ：詢問某個節點 x 到根的路徑中所有點的點權和。

Input

 第一行包含兩個整數 N, M 。表示點數和操作數。

接下來一行 N 個整數，表示樹中節點的初始權值。 接下來 N-1 行每行三個正整數 fr, to ， 表示該樹中存在一條邊 (fr, to) 。 再接下來 M 行，每行分别表示一次操作。其中第一個數表示該操 作的種類（ 1-3 ） ，之後接這個操作的參數（ x 或者 x a ） 。

Output

 對于每個詢問操作，輸出該詢問的答案。答案之間用換行隔開。

Sample Input

5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3      

Sample Output

6
9
13
      

Hint

 對于 100% 的資料， N,M<=100000 ，且所有輸入資料的絕對值都不

會超過 10^6 。

習慣了鍊上的問題，都忘了原來剖分的過程是dfs序列，是以子樹是一段連續的區間。

樹鍊剖分加上線段樹區間更新區間求和。

#include<cstdio>
#include<algorithm>
using namespace std;
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define loop(i,j,k) for (int i=j;i!=-1;i=k[i])
#define inone(x) scanf("%d",&x)
#define intwo(x,y) scanf("%d%d",&x,&y)
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
const int low(int x) { return x&-x; }
const int N = 2e5 + 10;
int n, m, x, y, z;
int ft[N], nt[N], u[N], sz = 0;
int ct[N], mx[N], fa[N], dep[N];
int top[N], L[N], R[N], g[N], v[N];
long long f[N << 2], a[N << 2];

void dfs(int x, int f)
{
	dep[x] = dep[f] + 1;
	fa[x] = f;	ct[x] = 1;	mx[x] = 0;
	loop(i, ft[x], nt)
	{
		if (u[i] == f) continue;
		dfs(u[i], x);
		ct[x] += ct[u[i]];
		if (ct[u[i]] > ct[mx[x]]) mx[x] = u[i];
	}
}

void Dfs(int x, int t)
{
	top[x] = !t ? x : top[fa[x]];
	L[x] = ++sz; g[sz] = x;
	if (mx[x]) Dfs(mx[x], 1);
	loop(i, ft[x], nt)
	{
		if (u[i] == fa[x]) continue;
		if (u[i] == mx[x]) continue;
		Dfs(u[i], 0);
	}
	R[x] = sz;
}

void build(int x, int l, int r)
{
	a[x] = 0;
	if (l == r) { f[x] = v[g[l]]; return; }
	int mid = l + r >> 1;
	build(lson); build(rson);
	f[x] = f[x << 1] + f[x << 1 | 1];
}

void pushdown(int x, int l, int r, int mid)
{
	a[x << 1] += a[x]; a[x << 1 | 1] += a[x];
	f[x << 1] += a[x] * (mid - l + 1);
	f[x << 1 | 1] += a[x] * (r - mid);
	a[x] = 0;
}

void add(int x, int l, int r, int ll, int rr, int u)
{
	if (ll <= l&&r <= rr)
	{
		a[x] += u; f[x] += 1LL * u * (r - l + 1);
	}
	else
	{
		int mid = l + r >> 1;
		if (a[x]) pushdown(x, l, r, mid);
		if (ll <= mid) add(lson, ll, rr, u);
		if (rr > mid) add(rson, ll, rr, u);
		f[x] = f[x << 1] + f[x << 1 | 1];
	}
}

long long sum(int x, int l, int r, int ll, int rr)
{
	if (ll <= l&&r <= rr) return f[x];
	int mid = l + r >> 1;
	long long res = 0;
	if (a[x]) pushdown(x, l, r, mid);
	if (ll <= mid) res += sum(lson, ll, rr);
	if (rr > mid) res += sum(rson, ll, rr);
	return res;
}

long long root(int x)
{
	long long res = 0;
	for (; x; x = fa[top[x]])
	{
		res += sum(1, 1, n, L[top[x]], L[x]);
	}
	return res;
}

int main()
{
	while (scanf("%d%d", &n, &m) != EOF)
	{
		dep[0] = ct[0] = sz = 0;
		rep(i, 1, n) inone(v[i]), ft[i] = -1, f[i] = 0;
		rep(i, 1, n - 1)
		{
			intwo(x, y);
			u[sz] = y; nt[sz] = ft[x]; ft[x] = sz++;
			u[sz] = x; nt[sz] = ft[y]; ft[y] = sz++;
		}
		dfs(1, 0); Dfs(1, sz = 0);
		build(1, 1, n);
		while (m--)
		{
			inone(x);
			if (x == 3)
			{
				inone(y);
				printf("%lld\n", root(y));
			}
			else
			{
				intwo(y, z);
				add(1, 1, n, L[y], x == 1 ? L[y] : R[y], z);
			}
		}
	}
	return 0;
}