D 树上求和

其实这是我打的第二道题……一眼可以用树剖做，于是就是树链剖分的板子题。
但其实似乎只求子树用dfs序就可以……？是我蠢了。
线段树维护平方和也是老套路了：

#include <cstdio>
#include <ctype.h>
#define DEBUG
#define int long long
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize],*p1 = buf,*p2 = buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,bufSize,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    r=0;
    for(c = nc();!isdigit(c);) c = nc();
    for(;isdigit(c);c=nc()) r = r * 10 + c - 48;
    return r;
}
const int maxn = 1e5 + 100,maxm = 2e5 + 100;
int n,m;
struct node
{
    int to,next;
}E[maxm];
int head[maxn];
inline void add(const int &x,const int &y)
{
    static int tot = 0;
    E[++tot].next = head[x],E[tot].to = y,head[x] = tot;
}
int w[maxn];
int size[maxn],fa[maxn],son[maxn],dfn[maxn],id[maxn],cnt;
long long sum[maxn<<2],tsum[maxn<<2],tag[maxn<<2];
const int mod = 23333;
#define ls p<<1
#define rs p<<1|1
inline void pushup(const int &p){sum[p] = sum[ls] + sum[rs];tsum[p] = tsum[ls] + tsum[rs];sum[p] %= mod,tsum[p] %= mod;}
inline void pushdown(const int &l,const int &r,const int &p)
{
    if(!tag[p]) return;
    int mid = l + r >> 1;
    tsum[ls] += (mid - l + 1) * tag[p] * tag[p] + 2 * sum[ls] * tag[p];
    tsum[rs] += (r - mid) * tag[p] * tag[p] + 2 * sum[rs] * tag[p];
    sum[ls] += (mid - l + 1) * tag[p];
    sum[rs] += (r - mid) * tag[p];
    tag[ls] += tag[p],tag[rs] += tag[p];
    tsum[ls] %= mod,tsum[rs] %= mod,sum[ls] %= mod,sum[rs] %= mod,tag[ls] %= mod,tag[rs] %= mod;
    tag[p] = 0;
}
void build(int l,int r,int p)
{
    if(l == r) return (void)(sum[p] = w[id[l]] % mod,tsum[p] = (w[id[l]] * w[id[l]]) % mod);
    int mid = l + r >> 1;
    build(l, mid, ls), build(mid + 1, r, rs);
    pushup(p);
}
void modify(int l,int r,int p,int ll,int rr,long long k)
{
    if(l >= ll && r <= rr)
    {
        tsum[p] += (r - l + 1) * k * k + 2 * sum[p] * k;
        sum[p] += (r - l + 1) * k;
        tag[p] += k;
        tsum[p] %= mod,sum[p] %= mod,tag[p] %= mod;
        return;
    }
    int mid = l + r >> 1;
    pushdown(l,r,p);
    if(ll <= mid) modify(l,mid,ls,ll,rr,k);
    if(rr > mid) modify(mid + 1,r,rs,ll,rr,k);
    pushup(p);
}
long long ask(int l,int r,int p,int ll,int rr)
{
    if(l >= ll && r <= rr) return tsum[p];
    int mid = l + r >> 1,ans = 0;
    pushdown(l,r,p);
    if(ll <= mid) ans = ask(l,mid,ls,ll,rr) % mod;
    if(rr > mid) ans = (ans + ask(mid + 1,r,rs,ll,rr)) % mod;
    return ans;
}
void dfs1(int u)
{
    size[u] = 1;
    for(int p = head[u];p;p=E[p].next)
    {
        int v = E[p].to;
        if(v == fa[u]) continue;
        fa[v] = u,dfs1(v),size[u] += size[v];
        if(size[son[u]] < size[v]) son[u] = v;
    }
}
void dfs2(int u)
{
    dfn[u] = ++cnt;
    id[cnt] = u;
    if(!son[u]) return;
    dfs2(son[u]);
    for(int p = head[u];p;p=E[p].next)
    {
        int v = E[p].to;
        if(v == son[u] || v == fa[u]) continue;
        dfs2(v);
    }
}
signed main()
{
    read(n),read(m);
    for(int i = 1;i<=n;++i) read(w[i]);
    for(int i = 1;i<n;++i)
    {
        int a,b;
        read(a),read(b);
        add(a,b),add(b,a);
    }
    dfs1(1),dfs2(1);
    build(1,n,1);
    while(m--)
    {
        int opt,x,y;
        read(opt),read(x);
        if(opt == 1) read(y),modify(1,n,1,dfn[x],dfn[x] + size[x] - 1,y);
        else printf("%lld\n",ask(1,n,1,dfn[x],dfn[x] + size[x] - 1) % mod);
    }
    return 0;
}