num[u] u被所有点对经过的次数

siz[u] 子树u的大小

[BIT]A 维护区间num[i]*w[i]

[BIT]B 维护区间siz[i]*w[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**************************************************************
    Problem: 5477
    User: ZqlwMatt
    Language: C++
    Result: Accepted
    Time:1516 ms
    Memory:16868 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
namespace optimize_io {
const int L=1<<15;char buf[L],*S,*T;
inline char gc() {if(S==T) {T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;} return *S++;}
inline int read() {
    char c; register int x=0,f=1; for(c=gc();!isdigit(c);c=gc())if(c=='-')f=-1;
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=gc();
    return x*f;
}}using optimize_io::read;
#define p 1000000007
inline void MOD(int &a) {if(a>=p)a-=p;}
int n, m;
#define N 200005
int cnt, nxt[2*N], to[2*N], h[N];
inline void add(int a,int b) {nxt[++cnt]=h[a],to[h[a]=cnt]=b;}
#define lowbit(x) (x&-x)
struct BIT {
    int a[N];
    inline void add(int x,int d) {for(;x<=n;x+=lowbit(x)) MOD(a[x]+=d);}
    inline int get(int x) {
        int r=0;
        for(;x;x-=lowbit(x)) MOD(r+=a[x]);
        return r;
    }
}A, B;
 
int idx, siz[N], num[N], dfn[N], efn[N];
void dfs(int u,int fa) {
    siz[u]=num[u]=1; dfn[u]=++idx;
    for(int i=h[u];i;i=nxt[i])if(to[i]!=fa) {
        dfs(to[i],u);
        MOD(num[u] += 1ll*siz[to[i]]*siz[u]%p);
        siz[u] += siz[to[i]];
    }
    MOD(num[u] += 1ll*siz[u]*(n-siz[u])%p);
    efn[u]=idx;
    A.add(dfn[u],num[u]); B.add(dfn[u],siz[u]);
}
 
int main() {
    n=read(), m=read();
    int u, v, opt;
    rep(i,2,n) u=read(),v=read(),add(u,v),add(v,u);
    dfs(1,0);
    while(m--) {
        opt=read(), u=read();
        if(opt==1) {
            v=read();
            A.add(dfn[u], 1ll*v*num[u]%p);
            B.add(dfn[u], 1ll*v*siz[u]%p);
        }
        else {
            long long ans = (A.get(efn[u])-A.get(dfn[u]-1))-1ll*(B.get(efn[u])-B.get(dfn[u]-1))*(n-siz[u]);
            ans %= p;
            if(ans<0) ans+=p;
            printf("%lld\n", ans);
        }
    }
    return 0;
}