J. Ka Chang

Given a rooted tree ( the root is node 11 ) of NN nodes. Initially, each node has zero point.

Then, you need to handle QQ operations. There're two types:

1\ L\ X1 L X: Increase points by XX of all nodes whose depth equals LL ( the depth of the root is zero ). (x \leq 10^8)(x≤108)

2\ X2 X: Output sum of all points in the subtree whose root is XX.

Input

Just one case.

The first lines contain two integer, N,QN,Q. (N \leq 10^5, Q \leq 10^5)(N≤105,Q≤105).

The next n-1n−1 lines: Each line has two integer aa,bb, means that node aa is the father of node bb. It's guaranteed that the input data forms a rooted tree and node 11 is the root of it.

The next QQ lines are queries.

Output

For each query 22, you should output a number means answer.

#include<bits/stdc++.h>

using namespace std;

const int N=;

vector<int>G[N];

vector<int>pos[N];

vector<int>vec;

int L[N],R[N];

int tot,n,m,lim=;

long long s[N],c[N];

void dfs(int now,int deep)

{

    L[now]=++tot;//一块的左标记

    pos[deep].push_back(L[now]);

    for(auto X:G[now])dfs(X,deep+);

    R[now]=tot;//右标记，这个内全是其子树

    return;

}

void add(int x,int d)

{

    for(;x<=n;x+=x&-x)c[x]+=d;

}

long long sum(int x)

{

    long long ans=;

    for(;x>;x-=x&-x)ans+=c[x];

    return ans;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=,u,v;i<n;i++)

        scanf("%d%d",&u,&v),G[u].push_back(v);

    dfs(,);

    for(int i=;i<=n;i++)

        if(pos[i].size()>lim)vec.push_back(i);

    for(int i=,op,x,y;i<m;i++)

    {

        scanf("%d%d",&op,&x);

        if(op==)

        {

            scanf("%d",&y);

            if(pos[x].size()<=lim)

                for(auto X:pos[x])add(X,y);//小于所给块大小，直接树状数组更新

            else s[x]+=y;//大于的直接扔进去等更新

        }

        else

        {

            long long ans=sum(R[x])-sum(L[x]-);//查询所有小块的值,多余的进行下面的更新

             for(auto X:vec)

                ans+=(upper_bound(pos[X].begin(), pos[X].end(),R[x])-lower_bound(pos[X].begin(),pos[X].end(),L[x]))*s[X];

                //vec的元素不会太多，顶多1e5，直接搞进去更新

            printf("%lld\n",ans);

        }

    }

}