题意：

一个树，对其有两个操作，操作1是将节点a的权值增加x
操作2是查询节点a到根节点R的简单路径上所有节点的权值的平方的和
答案对2^取模

题解：

如果ull类型的整数溢出了，就相当于取模2^64了。因为ull的范围是[0,2^64-1]，所以直接开unsigned long long就行
有两个方法：
1.树链剖分单点修改，树链查询，时间复杂度为O(nlognlogn)
2.修改一个点x，该点的影响范围为其子树中所有点，因为子树的点到树根必经过x点。我dfs序上建立线段树，每个点维护当前点到根节点的答案，修改某个点的权值时，只需要对以当前点为根的子树进行修改即可。
查询时单点查询，时间复杂度为O(n * logn)

树链剖分好久没用了，比赛时敲模板一直在报错。。。
第二个方法还是挺直接的，dfs先构造父子关系以及深度，然后线段树维护即可

代码：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#define int long long
using namespace std;

unsigned long long val[1000009];
unsigned long long reval[1000009];
int in[1000009];
int out[1000009];
int inout[2000009];
vector<int>maps[1000009];
int cnt=1;
unsigned long long tree[8000009];

void dfs(int now,int pre,unsigned long long cc)//dfs序，顺便记录每个节点的价值和 
{
    inout[cnt]=now;
    in[now]=cnt;
    cnt++;
    reval[now] = cc+val[now]*val[now];
    for(int i=0;i<maps[now].size();i++)
    {
        if(maps[now][i]==pre) continue;
        dfs(maps[now][i],now,reval[now]);
    }
    inout[cnt]=now;
    out[now]=cnt;
    cnt++;
}

void build(int l,int r,int now)
{
    //tree[now] = 0;
    if(l==r)
    {
        tree[now]=reval[inout[l]];
        return;
    }


    build(l,(l+r)/2,now*2);
    build((l+r)/2+1,r,now*2+1);
}

int check(int l,int r,int now,int aim)
{
    if(l==r)
    {
        return tree[now];
    }

    if(tree[now]>0)
    {
        tree[now*2]+=tree[now];
        tree[now*2+1]+=tree[now];
        tree[now]=0;
    }

    if(aim<=(l+r)/2)
    check(l,(l+r)/2,now*2,aim);
    else
    check((l+r)/2+1,r,now*2+1,aim);
}

void change(int l,int r,int now,int ll,int rr,unsigned long long num)
{
    if(ll<=l&&r<=rr)
    {
        tree[now]+=num;
        return ;
    }

    if(tree[now]>0)
    {
        tree[now*2]+=tree[now];
        tree[now*2+1]+=tree[now];
        tree[now]=0;
    }

    if(rr<=(l+r)/2)
    change(l,(l+r)/2,now*2,ll,rr,num);
    else if(ll>=(l+r)/2+1)
    change((l+r)/2+1,r,now*2+1,ll,rr,num);
    else
    {
        change(l,(l+r)/2,now*2,ll,(l+r)/2,num);
        change((l+r)/2+1,r,now*2+1,(l+r)/2+1,rr,num);
    }
}

signed main(){

    int n,m,r,i,j,k,l;

    scanf("%lld",&n);
    scanf("%lld",&m);
    scanf("%lld",&r);

    for(i=1;i<=n;i++)
    {
        scanf("%lld",&j);

        val[i] = (unsigned long long)(j);
    }

    for(i=2;i<=n;i++)
    {
        scanf("%lld",&j);
        scanf("%lld",&k);
        maps[j].push_back(k);
        maps[k].push_back(j);
    }

    dfs(r,-1,0);

    build(1,2*n,1);

    unsigned long long aaa;
    while(m--)
    {
        scanf("%lld",&j);

        if(j==1)
        {
            scanf("%lld",&k);
            scanf("%lld",&l);

            aaa=val[k]+(unsigned long long)l;
            aaa=aaa*aaa-val[k]*val[k];
            val[k] = val[k]+(unsigned long long)l;
            change(1,2*n,1,in[k],out[k],aaa);
        }
        else
        {
            scanf("%lld",&k);
            l=check(1,2*n,1,out[k]);
            printf("%lld\n",l);
        }

    }

    return 0;
}