#include using namespace std; typedef long long LL; typedef vector V; typedef vector Graph; struct INIT{INIT(){ios::sync_with_stdio(false);cin.tie(0);}}init; //heavy light decomposition namespace hld{ #define SZ 200010 int mem[4][SZ]; }; class HLD{ private: int *treesize; Graph *tree; public: int size,*group,*id,*par,*bg; private: void setTreeSize(int v){ treesize[v]=1; for(auto &u:(*tree)[v]){ setTreeSize(u); treesize[v]+=treesize[u]; } } void build(int v,int g,int& i){ group[v]=g; id[v]=i++; Graph &gr=(*tree); const int sz=gr[v].size(); if(sz){ int h=gr[v][0]; for(auto &u:gr[v]) if(treesize[h]; vector

decomposition(int r,int c){ vector

res; while(group[c]!=group[r]){ res.push_back(P(bg[group[c]],id[c])); c=par[group[c]]; } res.push_back(P(id[r],id[c])); return res; } }; void make_tree(int v,Graph& G,V& Par,V& D, Graph& C){ for(auto &e:G[v]){ if(e!=Par[v]){ C[v].push_back(e); D[e]=D[v]+1; Par[e]=v; make_tree(e,G,Par,D,C); } } } //lcaの準備 void build_PP(V& P,vector& PP){ int N = P.size(); for(int i = 0; i < N; i++)PP[0][i] = P[i]; for(int k = 0,f=1;f; k++){ f=0; for(int i = 0; i < N; i++){ if(PP[k][i]<0)PP[k+1][i]=-1; else {PP[k+1][i]=PP[k][PP[k][i]];f=1;} } } } int lca(int u,int v,V& D,vector &PP){ if(D[u] > D[v])swap(u,v); for(int k = 0,d;(d=D[v]-D[u]); k++)if((d >> k) & 1)v=PP[k][v]; if(u==v)return v; for(int k = PP.size() - 1; k >=0 ; k--){ if(PP[k][u]!=PP[k][v]){ u=PP[k][u]; v=PP[k][v]; } } return PP[0][u]; } #define SIZE 900000 #define L(v) (v*2+1) #define R(v) (v*2+2) #define SET 0 #define ADD 1 #define GET 2 typedef LL val; const LL MOD=1e9+7; struct node{ int bg,ed; val v,add,sum; inline val getval(){ return (v+sum*add%MOD)%MOD; } inline void init(int b,int e){ bg =b,ed=e; v=0,add=0,sum=0; } bool isleaf(){return bg==ed;} }mem[SIZE]; inline val comb(val l,val r){ return (l+r)%MOD; } class segTree{ private: node *t; val make_tree(int bg,int ed,vector &c,vector &s,int v=0){ node *p=t+v; p->init(bg,ed); if(!p->isleaf()){ int m=(bg+ed)/2; p->sum+=make_tree(bg,m,c,s,L(v)); p->sum+=make_tree(m+1,ed,c,s,R(v)); p->sum%=MOD; update(v); } else{ p->sum=c[bg]; p->v=s[bg]; } return p->sum; } public: using P=pair; segTree(int bg,int ed,vector &c,vector &s):t(mem){ make_tree(bg,ed,c,s); } inline void lazy_update(int v){ node *p=t+v,*l=t+L(v),*r=t+R(v); if(p->isleaf())return; (l->add+=p->add)%=MOD; (r->add+=p->add)%=MOD; p->add=0; } inline void update(int v){ node *p=t+v,*l=t+L(v),*r=t+R(v); if(p->isleaf()){ p->v+=p->add*p->sum%MOD; p->v%=MOD; p->add=0; } else{ p->v=comb(l->getval(),r->getval()); } } val treat(int type,int bg,int ed,val x,int v=0){ node *p=t+v,*l=t+L(v),*r=t+R(v); lazy_update(v); if(P(bg,ed)==P(p->bg,p->ed)){ if(type==ADD)(p->add+=x)%=MOD; update(v); return p->getval(); } int m; val res=0; if(bg<=(m=min(ed,l->ed))) res=comb(res,treat(type,bg,m,x,L(v))); if((m=max(bg,r->bg))<=ed) res=comb(res,treat(type,m,ed,x,R(v))); update(v); return res; } val get(int bg,int ed){ return treat(GET,bg,ed,val()); } val add(int bg,int ed,val x){ return treat(ADD,bg,ed,x); } }; const int root=0; int main(){ int N;cin>>N; N++; vector s(N),S(N),c(N),C(N); s[root]=c[root]=0; for(int i=1;i>s[i]; for(int i=1;i>c[i]; Graph g(N),tree(N); g[root].push_back(1); V par(N,-1),depth(N,0); vector pp(18,V(N,-1)); for(int i=2;i>a>>b; g[a].push_back(b); g[b].push_back(a); } make_tree(root,g,par,depth,tree); build_PP(par,pp); HLD hld(&tree,root); for(int i=0;i>Q; while(Q--){ int t; cin>>t; if(t){ int x,y; cin>>x>>y; int ca=lca(x,y,depth,pp); LL ans=0; auto p=hld.decomposition(ca,x); auto q=hld.decomposition(ca,y); auto r=hld.decomposition(ca,ca); for(auto &it:p)(ans+=st.get(it.first,it.second))%=MOD; for(auto &it:q)(ans+=st.get(it.first,it.second))%=MOD; for(auto &it:r)ans+=MOD-st.get(it.first,it.second); cout<>x>>y>>z; int ca=lca(x,y,depth,pp); auto p=hld.decomposition(ca,x); auto q=hld.decomposition(ca,y); auto r=hld.decomposition(ca,ca); for(auto &it:p)st.add(it.first,it.second,z); for(auto &it:q)st.add(it.first,it.second,z); for(auto &it:r)st.add(it.first,it.second,-z); } } return 0; }