D 树上求和

题目地址：

https://ac.nowcoder.com/acm/contest/6290/D

基本思路：

比较裸的一道题，没有什么思维量，
首先要维护子树状态，很明显我们可以求个序，然后用数据结构去维护，
观察一下题意，要维护区间平方和，进行区间查询和区间修改，所以考虑线段树。
那么维护区间平方和的线段树怎么写函数,其实也比较简单,
假设这段区间内的平方和开始为,
那么我们将整个区间加,就变为
化简一下提出来其实就是
所以我们在维护区间平方和的同时在维护一下那部分普通的区间和，然后就很容易进行了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 1e5 + 10;
const int mod = 23333;
int n,q;
struct edge {
    int next, v;
}edges[maxn << 1];
int cnt,tot,w[maxn];
int head[maxn];
void init() {
  memset(head, -1, sizeof(head));
  cnt = 0; tot = 0;
}
void add_edge(int u,int v) {
  edges[cnt].next = head[u];
  edges[cnt].v = v;
  head[u] = cnt++;
}
int L[maxn],R[maxn],dfn[maxn];
void dfs(int u,int ***] = ++tot;
  dfn[tot] = u;
  for (int i = head[u]; i != -1; i = edges[i].next) {
    int v = edges[i].v;
    if (v == fa) continue;
    dfs(v, u);
  }
  R[u] = tot;
}
struct node{
    int l,r,sum,res,add;
}t[maxn<<2];
inline void push_up(int p) {
  t[p].res = (t[p << 1].res + t[p << 1 | 1].res) % mod;
  t[p].sum = (t[p << 1].sum + t[p << 1 | 1].sum) % mod;
}
inline void push_down(int p) {
  if (t[p].add) {
    int v = t[p].add; t[p].add = 0;
    t[p << 1].add = (t[p << 1].add + v) % mod;
    t[p << 1 | 1].add = (t[p << 1 | 1].add + v) % mod;
    int ll = t[p << 1].r - t[p << 1].l + 1;
    int lr = t[p << 1 | 1].r - t[p << 1 | 1].l + 1;
    t[p << 1].res = (t[p << 1].res + ll * v * v % mod + 2 * t[p << 1].sum * v % mod) % mod;
    t[p << 1 | 1].res = (t[p << 1 | 1].res + lr * v * v % mod + 2 * t[p << 1 | 1].sum * v % mod) % mod;
    t[p << 1].sum = (t[p << 1].sum + ll * v) % mod;
    t[p << 1 | 1].sum = (t[p << 1 | 1].sum + lr * v) % mod;
  }
}
void build(int p,int l,int r) {
  t[p].l = l; t[p].r = r;
  if (l == r) {
    t[p].sum = w[dfn[l]];
    t[p].res = t[p].sum * t[p].sum % mod;
    return;
  }
  int mid = l + r >> 1;
  build(p << 1, l, mid);
  build(p << 1 | 1, mid + 1, r);
  push_up(p);
}
void change(int p,int l,int r,int v) {
  if (t[p].l == l && t[p].r == r) {
    t[p].res = (t[p].res + (r - l + 1) * v * v % mod + 2 * t[p].sum * v % mod) % mod;
    t[p].sum = (t[p].sum + (r - l + 1) * v % mod) % mod;
    t[p].add = (t[p].add + v) % mod;
    return;
  }
  push_down(p);
  int mid = (t[p].l + t[p].r) >> 1;
  if (r <= mid) change(p << 1, l, r, v);
  else if (l > mid) change(p << 1 | 1, l, r, v);
  else change(p << 1, l, mid, v), change(p << 1 | 1, mid + 1, r, v);
  push_up(p);
}
int ask(int p,int l,int r) {
  if (t[p].l == l && t[p].r == r) return t[p].res % mod;
  push_down(p);
  int mid = (t[p].l + t[p].r) >> 1;
  if (r <= mid) return ask(p << 1, l, r);
  else if (l > mid) return ask(p << 1 | 1, l, r);
  else return (ask(p << 1, l, mid) + ask(p << 1 | 1, mid + 1, r)) % mod;
}
signed main() {
  n = read(),q = read();
  rep(i,1,n) w[i] = read();
  init();
  rep(i,1,n-1) {
    int u = read(), v = read();
    add_edge(u, v);
    add_edge(v, u);
  }
  dfs(1,0);
  build(1,1,n);
  while (q--){
    int op = read();
    if(op == 1){
      int x = read(),y = read();
      change(1,L[x],R[x],y);
    }else{
      int x = read();
      int ans = ask(1,L[x],R[x]);
      print(ans);
      puts("");
    }
  }
  return 0;
}