#include #define all(v) v.begin(),v.end() using namespace std; typedef long long ll; typedef pair P; const ll MOD=1000000007; const ll INF=1000000000; const ll LINF=4000000000000000010; ll s[200010],c[200010],sum[200010],tmp[200010]; struct Segtree{//RAQxRSQ int n; vector node,lazy; void init(int n_){ n=1; while(n=0;i--){ node[i]=node[i*2+1]+node[i*2+2]; } } void eval(int k,int l,int r){ if(lazy[k]==0)return; node[k]+=lazy[k]%MOD*(sum[r]-sum[l]+MOD)%MOD; node[k]%=MOD; if(r-l>1){ lazy[2*k+1]+=lazy[k];//[l,(l+r)/2) lazy[2*k+2]+=lazy[k];//[(l+r)/2,r) } lazy[k]=0; } void add(int a,int b,ll z,int k=0,int l=0,int r=-1){ if(r<0)r=n; eval(k,l,r); if(b<=l||r<=a)return; if(a<=l&&r<=b){ lazy[k]+=z; eval(k,l,r); }else{ add(a,b,z,2*k+1,l,(l+r)/2); add(a,b,z,2*k+2,(l+r)/2,r); node[k]=node[2*k+1]+node[2*k+2]; } } ll getsum(int a,int b,int k=0,int l=0,int r=-1){ if(r<0)r=n; eval(k,l,r); if(b<=l||r<=a)return 0; if(a<=l&&r<=b)return node[k]; ll vl=getsum(a,b,2*k+1,l,(l+r)/2); ll vr=getsum(a,b,2*k+2,(l+r)/2,r); return vl+vr; } }; struct HLDecomposition{ int n,pos; vector> G; //新index,heavy-edgeの最初の要素のindex,部分木のサイズ,heavy-edgeでの次の頂点,親,深さ,元index vector nid,fst,siz,hv,par,dep,id; Segtree tree; HLDecomposition(int n_){ n=n_,pos=0; G.resize(n); nid.resize(n,-1); fst.resize(n); siz.resize(n,1); hv.resize(n,-1); par.resize(n); dep.resize(n); id.resize(n); } void add_edge(int u,int v){ G[u].push_back(v); G[v].push_back(u); } void build(int rt){//rtを根とする木についてHL分解 par[rt]=-1; dep[rt]=0; dfs(rt); bfs(rt); } void dfs(int v){//heavy-edgeを選んでいく int res=0; for(auto u:G[v]){ if(u==par[v])continue; par[u]=v; dep[u]=dep[v]+1; dfs(u); siz[v]+=siz[u]; if(res q; q.push(r); while(!q.empty()){ int h=q.front();q.pop(); for(int i=h;i!=-1;i=hv[i]){ nid[i]=pos++; id[nid[i]]=i; fst[i]=h; for(int j:G[i]){ if(j!=par[i]&&j!=hv[i])q.push(j); } } } } int lca(int u,int v){ while(1){ if(nid[u]>nid[v])swap(u,v); if(fst[u]==fst[v])return u; v=par[fst[v]]; } } void query0(int x,int y,ll z){ while(1){ if(nid[x]>nid[y])swap(x,y); tree.add(max(nid[fst[y]],nid[x]),nid[y]+1,z); if(fst[x]!=fst[y]){ y=par[fst[y]]; }else{ break; } } } ll query1(int x,int y){ ll res=0; while(1){ if(nid[x]>nid[y])swap(x,y); res+=tree.getsum(max(nid[fst[y]],nid[x]),nid[y]+1); res%=MOD; if(fst[x]!=fst[y]){ y=par[fst[y]]; }else{ break; } } return res; } }; int main(){ int n;cin>>n; for(int i=0;i>s[i]; for(int i=0;i>c[i]; HLDecomposition tree(n); for(int i=0;i>a>>b;a--;b--; tree.add_edge(a,b); } tree.build(0); for(int i=0;i>q; while(q--){ ll t,x,y,z; cin>>t; if(t==0){ cin>>x>>y>>z;x--;y--; tree.query0(x,y,z); }else{ cin>>x>>y;x--;y--; cout<