#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; template struct LazySegmentTree{ using F=function; using G=function; using H=function; int sz; vector data; vector lazy; const F f; const G g; const H h; const Monoid e1; const OperatorMonoid e0; LazySegmentTree(int n, const F f, const G g, const H h, const Monoid &e1, const OperatorMonoid &e0): f(f), g(g), h(h), e1(e1), e0(e0){ sz=1; while(sz v){ for(int i=0; i=0; i--) data[i]=f(data[2*i+1], data[2*i+2]); } void eval(int k, int l, int r){ if(lazy[k]!=e0){ data[k]=g(data[k], lazy[k], l, r); if(k> > struct HeavyLightDecomposition { G &g; vector< int > sz, in, out, head, rev, par; HeavyLightDecomposition(G &g) : g(g), sz(g.size()), in(g.size()), out(g.size()), head(g.size()), rev(g.size()), par(g.size()) {} void dfs_sz(int idx, int p) { par[idx] = p; sz[idx] = 1; if(g[idx].size() && g[idx][0] == p) swap(g[idx][0], g[idx].back()); for(auto &to : g[idx]) { if(to == p) continue; dfs_sz(to, idx); sz[idx] += sz[to]; if(sz[g[idx][0]] < sz[to]) swap(g[idx][0], to); } } void dfs_hld(int idx, int par, int ×) { in[idx] = times++; rev[in[idx]] = idx; for(auto &to : g[idx]) { if(to == par) continue; head[to] = (g[idx][0] == to ? head[idx] : to); dfs_hld(to, idx, times); } out[idx] = times; } void build() { dfs_sz(0, -1); int t = 0; dfs_hld(0, -1, t); } int la(int v, int k) { while(1) { int u = head[v]; if(in[v] - k >= in[u]) return rev[in[v] - k]; k -= in[v] - in[u] + 1; v = par[u]; } } int lca(int u, int v) { for(;; v = par[head[v]]) { if(in[u] > in[v]) swap(u, v); if(head[u] == head[v]) return u; } } template< typename T, typename Q, typename F > T query(int u, int v, const T &ti, const Q &q, const F &f, bool edge = false) { T l = ti;//, r = ti; for(;; v = par[head[v]]) { if(in[u] > in[v]) swap(u, v);//, swap(l, r); if(head[u] == head[v]) break; l = f(q(in[head[v]], in[v] + 1), l); } return f(q(in[u] + edge, in[v] + 1), l); } template< typename Q > void add(int u, int v, const Q &q, bool edge = false) { for(;; v = par[head[v]]) { if(in[u] > in[v]) swap(u, v); if(head[u] == head[v]) break; q(in[head[v]], in[v] + 1); } q(in[u] + edge, in[v] + 1); } }; int main() { int n; scanf("%d", &n); ll c1[200020], c[200020], cs[200020], s1[200020]; vector s(n); for(int i=0; i> G(n); for(int i=0; i hld(G); hld.build(); for(int i=0; i=MOD) cs[i+1]-=MOD; } auto f=[MOD](ll a, ll b){ ll ret=a+b; if(ret>=MOD) ret-=MOD; return ret; }; auto g=[&](ll a, ll x, int l, int r){ return (a+x*(cs[r]-cs[l]+MOD))%MOD; }; auto h=[MOD](ll x, ll y){ ll ret=x+y; if(ret>=MOD) ret-=MOD; return ret; }; LazySegmentTree seg(n, f, g, h, 0, 0); seg.build(s); int Q; scanf("%d", &Q); for(int z=0; z