#pragma GCC optimize ("O3") #pragma GCC target ("avx") #pragma GCC optimize ("fast-math") #include using namespace std; #define rep(i,n) for(long long i = 0; i < (long long)(n); i++) typedef long long LL; typedef vector vll; typedef vector vvll; typedef vector Graph; template ostream &operator<<(ostream &o, const pair &v) { o << "(" << v.first << ", " << v.second << ")"; return o; } template struct seq{}; template struct gen_seq : gen_seq{}; template struct gen_seq<0, Is...> : seq{}; template void print_tuple(basic_ostream& os, Tuple const& t, seq){ using s = int[]; (void)s{0, (void(os << (Is == 0? "" : ", ") << get(t)), 0)...}; } template auto operator<<(basic_ostream& os, tuple const& t) -> basic_ostream& { os << "("; print_tuple(os, t, gen_seq()); return os << ")"; } ostream &operator<<(ostream &o, const vvll &v) { rep(i, v.size()) { rep(j, v[i].size()) o << v[i][j] << " "; cout << endl; } return o; } template ostream &operator<<(ostream &o, const vector &v) { o << '['; rep(i, v.size()) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "]"; return o; } template ostream &operator<<(ostream &o, const set &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]"; return o; } template ostream &operator<<(ostream &o, const map &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]"; return o; } template ostream &operator<<(ostream &o, const unordered_map &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it; o << "]"; return o; } struct INIT {INIT() {ios::sync_with_stdio(false);cin.tie(0);}}init; // heavy light decomposition // // 今までの番号を、Heavy-Lightパスの根から葉の方向へと付け替える in [0, n) // これ自体にはデータを載せず、パスの添字のみを取得するインターフェースのみ提供 class HLD { private: vector treesize; // tree->size(): 子の数 Graph *tree; public: // i: ノードの添字 // j: Heavy pathの添字 int size = 0; // Heavy pathの数 vector group; // tree->size(): ノードiが属するグループj vector id; // tree->size(): ノードiに再割り振りされた新ノード番号id in [0, tree->size()) vector par; // size: Heavy path jの根の親のノードi vector bg; // size: Heavy path jの根のノードi 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); if (!gr[v].size()) return; // 最大サイズの子hを求める int h=gr[v][0]; for (auto &u:gr[v]) if(treesize[h]size(); treesize.resize(n); group.resize(n); id.resize(n); setTreeSize(root); int i=0; // 再度割り振り直す添字番号 par.push_back(-1); bg.push_back(i); build(root, size++, i); } // O(log n) // // [r, c]の再割り振りされた添字区間を返す。 // // rがcより根側である必要がある // c側から、以下の漸化式によってパスを分解する // ret += {groupの根, c}, c = groupの根の親 using P=pair; 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 print(void) { rep(i, tree->size()) { cout << group[i] << " " << id[i] << endl; } cout << "####" << endl; rep(i, size) { cout << par[i] << " " << bg[i] << endl; } } }; void make_tree(int v, Graph& G, vll& Par, vll& 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(vll& 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, vll& 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); vll par(N, -1), depth(N, 0); for (int i=2;i> a >> b; g[a].push_back(b); g[b].push_back(a); } make_tree(root, g, par, depth, tree); vector pp(18, vll(N, -1)); // LCA用ダブリング build_PP(par, pp); HLD hld(&tree, root); /* cout << endl; cout << "########" << endl; hld.print(); cout << "########" << endl; */ 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, MOD-z); } } return 0; }