记录编号	617706	评测结果	AAAAAAAAAA
题目名称	4005.[模板]重链剖分	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	1.164 s
提交时间	2026-07-22 10:48:39	内存使用	10.96 MiB

#include<iostream>
#include<vector>
using namespace std;

template <int n, int k = 0, class F>
void UL(int i, F lambda){
    if(k < n) lambda(i + k), UL<n, k + (k < n)>(i, lambda);
}

#define lc u << 1
#define rc u << 1 | 1
const int N = 1e5 + 5;
int n, m, p;
vector<int> G[N];
int dep[N], f[N], son[N], top[N], sz[N];
int dfn[N], o[N], x[N], stk = 0;

void inc(int &a, int c){
    a += c;
    if(a >= p) a -= p;
}

void inp(int &a, int c){
    a = c;
    if(a >= p) a -= p;
}

void dfs1(int u, int fa){
    dep[u] = dep[fa] + 1;
    f[u] = fa;
    sz[u] = 1;
    for(int &v : G[u]){
        if(v != fa){
            dfs1(v, u);
            sz[u] += sz[v];
            if(sz[son[u]] < sz[v]){
                son[u] = v;
            }
        }
    }
}

void dfs2(int u, int tp){
    top[u] = tp;
    dfn[u] = ++stk;
    x[stk] = o[u];
    if(son[u]) dfs2(son[u], tp);
    for(int &v : G[u]){
        if(v != f[u] && v != son[u]){
            dfs2(v, v);
        }
    }
}

struct node{
    int l, r;
    int sum, add;
}t[N << 2];

void up(int u){
    inp(t[u].sum, t[lc].sum + t[rc].sum);
}

void down(int u){
    if(t[u].add){
        inc(t[lc].sum, (1LL * (t[lc].r - t[lc].l + 1) * t[u].add) % p);
        inc(t[rc].sum, (1LL * (t[rc].r - t[rc].l + 1) * t[u].add) % p);
        inc(t[lc].add, t[u].add);
        inc(t[rc].add, t[u].add);
        t[u].add = 0;
    }
}

void build(int u, int l, int r){
    t[u] = {l, r, 0, 0};
    if(l == r){
        t[u].sum = x[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    up(u);
}

int qry(int u, int l, int r){
    if(l <= t[u].l && t[u].r <= r){
        return t[u].sum;
    }
    down(u);
    int mid = (t[u].l + t[u].r) >> 1;
    int ans = 0;
    if(l <= mid) inc(ans, qry(lc, l, r));
    if(r > mid) inc(ans, qry(rc, l, r));
    return ans;
}

void upd(int u, int l, int r, int k){
    if(l <= t[u].l && t[u].r <= r){
        inc(t[u].sum, 1LL * (t[u].r - t[u].l + 1) * k % p);
        inc(t[u].add, k);
        return;
    }
    down(u);
    int mid = (t[u].l + t[u].r) >> 1;
    if(l <= mid) upd(lc, l, r, k);
    if(r > mid) upd(rc, l, r, k);
    up(u);
}

int askpa(int u, int v){
    int ans = 0;
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        inc(ans, qry(1, dfn[top[u]], dfn[u]));
        u = f[top[u]];
    }
    if(dep[u] < dep[v]) swap(u, v);
    inc(ans, qry(1, dfn[v], dfn[u]));
    return ans;
}

void updpa(int u, int v, int k){
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        upd(1, dfn[top[u]], dfn[u], k);
        u = f[top[u]];
    }
    if(dep[u] < dep[v]) swap(u, v);
    upd(1, dfn[v], dfn[u], k);
}

int main(){
    cin.tie(0) -> ios::sync_with_stdio(0);
    cin >> n >> m;
    p = 1000000007;
    int r = 1;
    for(int i = 1; i <= n; i += 4){
        UL<4>(i, [&](int i){
            if(i <= n) cin >> o[i];
            o[i] %= p;
        });
    }
    for(int i = 1; i < n; i += 4){
        UL<4>(i, [&](int i){
            if(i < n){
                int a, b; cin >> a >> b;
                G[a].push_back(b);
                G[b].push_back(a);
            }
        });
    }
    dfs1(r, 0);
    dfs2(r, r);
    build(1, 1, n);
    for(int i = 1; i <= m; i += 4){
        UL<4>(i, [&](int i){
            if(i <= m){
                int op, x, y, z;
                cin >> op;
                if(op == 1){
                    cin >> x >> y >> z;
                    z %= p;
                    updpa(x, y, z);
                }
                else{
                    cin >> x >> y;
                    cout << askpa(x, y) << '\n';
                }
            }
        });
    }
    return 0;
}