help.cpp

#include <bits/stdc++.h>
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;register bool _=0;register T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void print(T n){register bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);pc(10);}
template<typename First, typename ... Ints>
void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}

using namespace std;
typedef long long ll;
const int MM = 1e5+1, mod = 1e9+7;

int N, M, sz[MM], tot, par[MM], dep[MM], lca[18][MM];
ll ans[MM], c[MM], prod[18][MM];
bool vis[MM];
vector<int> adj[MM];

int getsz(int cur, int pre){
    sz[cur] = 1;
    for(int u: adj[cur]){
        if(u != pre && !vis[u])
            sz[cur] += getsz(u, cur);
    }
    return sz[cur];
}

int findcent(int cur, int pre){
    for(int u: adj[cur]){
        if(!vis[u] && u != pre && sz[u]*2 > tot)
            return findcent(u, cur);
    }
    return cur;
}

void go(int root, int pre){
    
    getsz(root, -1);
    tot = sz[root];
    
    if(tot == 1){
        par[root] = pre;
        return;
    }
    
    int cent = findcent(root, -1);
    par[cent] = pre;
    vis[cent] = 1;
    //block off
    
    for(int u: adj[cent]){
        if(!vis[u])
            go(u, cent);
    }
}

void dfs(int cur, int pre){
    dep[cur] = dep[pre]+1;
    lca[0][cur] = pre;
    prod[0][cur] = c[cur]; //jumping up
    
    for(int u: adj[cur]){
        if(u ^ pre)
            dfs(u, cur);
    }
}

inline int get_lca(int a, int b){
    if(dep[a] < dep[b])
        swap(a, b);
    for(int i = 16; i >= 0; i--){
        if(~lca[i][a] && (dep[lca[i][a]] >= dep[b]))
            a = lca[i][a];
    }
    if(a == b)
        return a;
    for(int i = 16; i >= 0; i--){
        if(~lca[i][a] && ~lca[i][b] && (lca[i][a] ^ lca[i][b])){
            a = lca[i][a];
            b = lca[i][b];
        }
    }
    return lca[0][a];
}

/*
 * since n is centroid, check the lca of a and n
 * if lca is n, check depth for which of a and n to include in lca query
 *      a jumps up before reaching n
 * if lca is higher (only other option)
 *      query up [a, lca] * down (up other sise) (n, lca]
 *
 * second queries are from ancestors to node
 * just to inclusive/exclusive the other way (in the query)
 */
//a, n
inline ll query(int a, int b, int type){
    
    if(a == b){
        //printf("q 1 1 = 1\n");
        return 1;
    }
    
    ll ret = 1;
    int rt = get_lca(a, b);
    
    //printf("q %d %d (%d) lca %d, ", a, b, type, rt);
    
    if(type == 1 and rt == b){
    }
    else if(type == 1){
        //count lca and don't count b  (also if a is lca)
        b = lca[0][b];
        ret *= c[rt];
    }
    else if(type == 2 and rt == a){
        //just let b jump (won't cover a)
    }
    else if(type == 2){
        //count lca and don't count a
        a = lca[0][a];
        ret *= c[rt];
    }
    
    for(int i = 17; i >= 0; i--){
        if(dep[a] >= dep[rt] + (1 << i)){
            ret = ret * prod[i][a] % mod;
            a = lca[i][a];
        }
    }
    for(int i = 17; i >= 0; i--){
        if(dep[b] >= dep[rt] + (1 << i)){
            ret = ret * prod[i][b] % mod;
            b = lca[i][b];
        }
    }
    
    //printf("= %lld\n", ret);
    
    return ret;
}

int main(){
    
    memset(lca, -1, sizeof lca);
    c[0] = 1;
    
    scan(N, M);
    
    for(int i = 1; i <= N; i++)
        scan(c[i]);
    
    for(int i = 0,a,b; i < N-1; i++){
        scan(a, b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    //dfs(1, 0);
    
    for(int i = 1; i <= N; i++){
        if(adj[i].size() == 1){
            dfs(i, 0);
            go(i, 0);
            break;
        }
    }
    
    for(int i = 1; i < 18; i++){
        for(int j = 1; j <= N; j++){
            if(~lca[i-1][j]){
                lca[i][j] = lca[i-1][lca[i-1][j]];
                prod[i][j] = prod[i-1][j] * prod[i-1][lca[i-1][j]] % mod;
            }
        }
    }
    
    /*
    puts("p");
    for(int i = 1; i <= N; i++)
        printf("%d ", par[i]);
    pc(10);
    pc(10);
     */
    
    for(int t = 0,op,a,b; t < M; t++){
        scan(op, a);
        if(op == 1){
            scan(b);
            int n = a;
            do{
                //printf("from %d - %d = %lld\n", a, n, mul);
                ans[n] += b * query(a, n, 1) % mod;
                ans[n] %= mod;
                n = par[n];
            } while(n);
        }
        else{
            ll ret = ans[a];
            int n = par[a], pre = a;
            while(n){
                ret += query(a, n, 2) * ((ans[n] - ((ans[pre]*c[pre])%mod) + mod) % mod) % mod;
                ret %= mod;
                //printf("q %d %d - %lld %lld, %lld %lld\n", n, pre, ans[n], ans[pre]*c[pre], mul, ans[n] - ans[pre]*c[pre]);
                pre = n;
                n = par[n];
            }
            
            print(ret);
        }
        
        /*
        printf("n ");
        for(int i = 1; i <= N; i++)
            printf("%lld ", ans[i]);
        pc(10);
         */
    }
    
    return 0;
}
/*
 * when going up through parents, store sum of subtree vals originating from direct child
 * then, add to node n      query(u, n)*(sum[u] - prod[0][v]*sum[v])
 *
 * fix lca and do it properly
 *
 * since n is centroid, check the lca of a and n
 * if lca is n, check depth for with of a and n to include in lca query
 * if lca is higher (only other option)
 *      query up [a, lca] * down (up other sise) (n, lca]
 *
 * second queries are from ancestors to node
 * just to inclusive/exclusive the other way (in the query)
 *
 */
/*
4 5
2 3 4 5
1 2
2 3
3 4
1 2 1
2 1
2 2
2 3
2 4


 */