C++14(g++5.4) 解法, 执行用时: 210ms, 内存消耗: 12924K, 提交时间: 2019-06-01 22:38:15

#include <cstdio>
#include <cstring>
#define LL long long
#define root 1, 1, n
#define ls now << 1, l, mid
#define rs now << 1 | 1, mid + 1, r
using namespace std;
const int MAXN = 100001;
int n, m, cnt, tot;
int head[MAXN], next[MAXN << 1], to[MAXN << 1], tid[MAXN], size[MAXN];
LL a[MAXN << 2], b[MAXN << 2], val[MAXN], dis[MAXN];
inline void add(int x, int y)
{
	to[cnt] = y;
	next[cnt] = head[x];
	head[x] = cnt++;
}
inline void dfs(int u)
{
	int i, v;
	tid[u] = ++tot;
	size[u] = 1;
	for (i = head[u]; i != -1; i = next[i])
	{
		v = to[i];
		if (!size[v])
		{
			dis[v] = dis[u] + 1;
			dfs(v);
			size[u] += size[v];
		}
	}
}
inline void push_down(int now)
{
	a[now << 1] += a[now];
	a[now << 1 | 1] += a[now];
	b[now << 1] += b[now];
	b[now << 1 | 1] += b[now];
	a[now] = b[now] = 0;
}
inline void update(LL x, LL y, int ql, int qr, int now, int l, int r)
{
	if (ql <= l && r <= qr)
	{
		a[now] += x;
		b[now] += y;
		return;
	}
	push_down(now);
	int mid = (l + r) >> 1;
	if (ql <= mid) update(x, y, ql, qr, ls);
	if (mid < qr) update(x, y, ql, qr, rs);
}
inline LL query(int u, int x, int now, int l, int r)
{
	if (l == r) return dis[u] * a[now] + b[now];
	push_down(now);
	int mid = (l + r) >> 1;
	if (x <= mid) return query(u, x, ls);
	else return query(u, x, rs);
}
int main()
{
	int i, x, z;
	int y;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= n; i++)    scanf("%lld", &val[i]);
	memset(head, -1, sizeof(head));
	for (i = 1; i < n; i++)
	{
		scanf("%d %d", &x, &y);
		add(x, y);
		add(y, x);
	}
	dis[1] = 1;
	dfs(1);
	for (i = 1; i <= n; i++) update(0, val[i], tid[i], tid[i] + size[i] - 1, root);
	for (i = 1; i <= m; i++)
	{
		scanf("%d %d", &z, &x);
		if (z == 1)
		{
			scanf("%d", &y);
			update(0, y, tid[x], tid[x] + size[x] - 1, root);
		}
		else if (z == 2)
		{
			scanf("%d", &y);
			update(y, -((dis[x] - 1) * y), tid[x], tid[x] + size[x] - 1, root);
		}
		else printf("%lld\n", query(x, tid[x], root));
	}
	return 0;
}

C++(clang++11) 解法, 执行用时: 206ms, 内存消耗: 15092K, 提交时间: 2021-03-30 17:34:43

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<string>
#include<queue>
#include<vector>
#define ll long long

using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 100005;

int N,M;
int a[maxn],fa[maxn]; 
vector<int>G[maxn];
int L[maxn],R[maxn],cnt = 0;
ll c[maxn][2],deep[maxn];
void dfs(int u,int pre)
{
    L[u] = ++cnt;
    deep[u] = deep[pre]+1;
    for(int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        if(v == pre) continue;
        dfs(v,u);
    }
    R[u] = cnt;
}

int lowbit(int x)
{
    return x&(-x);
}
void update(int x,ll v,int y)
{
    while(x <= N)
    {
        c[x][y]+=v;
        x+=lowbit(x);
    }
}
ll getsum(int x,int y)
{
    ll sum = 0;
    while(x>=1)
    {
        sum+=c[x][y];
        x-=lowbit(x);
    }
    return sum;
}
int main()
{
    cin>>N>>M;
    for(int i = 1; i<= N; i++) cin>>a[i];
    for(int i = 1; i <= N-1; i++)
    {
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    for(int i = 1; i<= N; i++)
    {
        update(L[i],a[i],0);
        update(R[i]+1,-a[i],0);
    }
    while(M--)
    {
        int q,x,a;
        cin>>q>>x;
        if(q == 1)
        {
            cin>>a;
            update(L[x],a,0);
            update(R[x]+1,-a,0);
        }
        else if(q == 2)
        {
            cin>>a;
            update(L[x],-(deep[x]-1)*a,0);
            update(R[x]+1,(deep[x]-1)*a,0);
            
            update(L[x],a,1);
            update(R[x]+1,-a,1);
        }
        else if(q == 3)
        {
            ll ans = getsum(L[x],0) + deep[x]*getsum(L[x],1);
            cout<<ans<<endl;
        }
    }
    return 0;
}