#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7, BLOCK = 320;

int n, m, a[100001], p[100001], idx[100001], order[100001], lb[100001], rb[100001]; // lb and rb are indexed by bfs order, not vertex
bool mark[100001];
vector<int> g[100001];

struct coolsqrt { // sqrt decomposition
    int f[100001], t[100001];
    void init() { for(int i = 1; i <= n; i++) f[i] = a[order[i]]; }
    void update(int l, int r, int v) {
        for(int i = l; i % BLOCK; i++) {
            f[i] = (f[i]+v)%MOD;
            if(i == r) return;
        }
        int block = l/BLOCK + 1;
        while(block < r/BLOCK) t[block++] += v, t[block] %= MOD;
        for(int i = BLOCK*(r/BLOCK); i <= r; i++) f[i]  = (f[i]+v)%MOD;
    }
    int query(int i) { return (f[i] + t[i/BLOCK])%MOD; }
    void putin() { for(int i = 1; i <= n; i++) cout << query(i) << ' '; cout << endl; }
} coolsqrt;

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1,u,v; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    queue<int> q;
    q.push(1);
    for(int i = 1, u = q.front(); i <= n; i++, q.pop(), u = q.front()) {
        mark[u] = true;
        idx[u] = i;
        order[i] = u;
        for(int v: g[u]) if(!mark[v]) q.push(v), p[v] = u;
    }
    assert(q.empty());
    for(int i = 1; i <= n; i++) if(p[order[i]]) {
        if(!lb[p[order[i]]]) lb[p[order[i]]] = i;
        rb[p[order[i]]] = i;
    }
    coolsqrt.init();
    cin >> m;
    int inst,v;
    while(m--) {
        cin >> inst >> v;
        if(inst == 1) {
            coolsqrt.update(idx[p[v]], idx[p[v]], coolsqrt.query(idx[v]));
            coolsqrt.update(lb[v], rb[v], coolsqrt.query(idx[v]));
            // coolsqrt.putin();
        } else {
            cout << coolsqrt.query(idx[v]) << endl;
        }
    }
    // for(int i = 1; i <= n; i++) cout << order[i] << ' ';
    // cout << endl;
    // for(int i = 1; i <= n; i++) cout << lb[i] << ' ' << rb[i] << endl;
}

Edited by author 01.09.2016 20:03

Edited by author 01.09.2016 20:03