C++14(g++5.4) 解法, 执行用时: 141ms, 内存消耗: 8368K, 提交时间: 2020-07-16 19:24:40

#include<bits/stdc++.h>
using namespace std;
long long a[100005];
int n,q,u,v;
vector<int> g[100005];
int fa[100005];//记录父节点,0为没有父节点
bool vis[100005];//懒标记
long long add[100005];
const int mod=23333;
typedef long long ll;
void dfs(int x,int f){
  for(auto &i:g[x]){
    if(i==f)continue;
    fa[i]=x;
    dfs(i,x);
  }
}
void updown(int x){
  if(fa[x])updown(fa[x]);
  if(vis[x]){
    for(int i: g[x]){
        if(fa[x]==i)continue;//?
        a[i]+=add[x];
        vis[i]=1;
        add[i]+=add[x];
    } vis[x]=0;add[x]=0;
  }

}
ll qu(ll  x,ll  y){
    long long ans=0;
    if(vis[y]){
        vis[y]=0;
        for(auto i: g[y]){
            if(fa[y]==i)continue;
            add[i]+=add[y];
            a[i]+=add[y];
            vis[i]=1;
        }add[y]=0;
    }
    ans=(a[x]*a[x])%mod;
    for(auto i:g[x]){
            if(i==fa[x])continue;
        ans=(qu(i,x)+ans)%mod;
    }
    return ans;
}
int main(){
  std::ios::sync_with_stdio(0);
   cin>>n>>q;
   for(int i=1;i<=n;i++){
    cin>>a[i];
   }
    for(int i=1;i<n;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    long long  z,x,y;
    while(q--){
           cin>>z;
    if(z==1){
        cin>>x>>y;
        a[x]+=y;
        vis[x]=1;
        add[x]+=y;
    }else{
    cin>>x;
    updown(x);
    cout<<qu(x,fa[x])<<endl;
    }
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 277ms, 内存消耗: 9800K, 提交时间: 2020-07-22 17:23:41

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3;
const int mod=23333;
vector<int>g[N];
int a[N],f[N]; 
void dfs(int s,int fa)
{
	for(auto v : g[s])
	{
		if(v!=fa)
		{
			f[v]=s;
			dfs(v,s);
		}
	}
	return ;
}
void dfs1(int s,int fa,int num)
{
	for(auto v:g[s])
	{
		if(v!=fa)
		{
			dfs1(v,s,num);
			a[v]=(a[v]+num)%mod;
		}
	}
	return;
}
int dfs2(int s,int fa)
{
	int ans=0;
	for(auto v:g[s])
	{
		if(v!=fa)
		{
			int num=dfs2(v,s);
			ans=(ans+num)%mod;
		}
	}
	return (ans+(1ll)*a[s]*a[s])%mod;
}
int main()
{
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	f[1]=-1;
	dfs(1,-1);
	for(int i=0;i<q;i++)
	{
		int k,x,y;
		cin>>k;
		if(k==1)
		{
			cin>>x>>y;
			dfs1(x,f[x],y);
			a[x]=(a[x]+y)%mod;
		}
		else
		{
			cin>>x;
			cout<<dfs2(x,f[x])<<endl;
		}
	}
	return 0;
}