#include #include #include #include #include #include #include #include #include #include using namespace std; #define MOD 1000000007 vector s, c; class LCA{ int root; //depth of node[i] vector d; //parent of node[i] vector > p; int log_n; //initialization of depths and parents void init(vector > &g, int pos, int last, int v){ d[pos] = v; p[0][pos] = last; for(int i=0; i > //g[i][j] := node[i]'s edge gose to node[ g[i][j] ] LCA(vector > &g, int r){ int n = g.size(); root = r; d = vector(n); log_n = (log(n)/log(2) + 1); p = vector >(log_n, vector(n)); init(g, root,-1,0); for(int k=0; k+1 < log_n; k++){ for(int v=0; v > &g){ int n = g.size(); root = 0; d = vector(n); log_n = (log(n)/log(2) + 1); p = vector >(log_n, vector(n)); //initialize as root = 0 init(g, root,-1,0); for(int k=0; k+1 < log_n; k++){ for(int v=0; v d[v]) swap(u,v); for(int k=0; k> k & 1){ v = p[k][v]; } } if(u==v) return u; for(int k=log_n-1; k>=0; k--){ if(p[k][u] != p[k][v]) { u = p[k][u]; v = p[k][v]; } } return p[0][u]; } //return depth of node[u] int depth(int u){ return d[u]; } }; struct my_value{ long long c; long long val; my_value(): c(0), val(0){ } my_value(long long c_, long long val_) : c(c_), val(val_){ } }; template class Segment_Tree_Lazy{ private: //default values are set in the constractor const T default_value; //default (NULL) node value const V default_lazy_value; //default lazy value struct node{ T value; V lazy_value; bool lazy; int lb; int ub; node* par; node* lch; node* rch; node(T default_value, V default_lazy_value) : value(default_value), lazy_value(default_lazy_value), lazy(false), lb(0),ub(0), par(NULL),lch(NULL),rch(NULL){ } }; T evaluate(T left_val, T right_val){ return my_value((left_val.c, right_val.c)%MOD, (left_val.val + right_val.val)%MOD); } void new_lazy(node* t, V z){ if(t==NULL) return; if(t->lazy){ t->lazy_value = t->lazy_value + z; }else{ t->lazy_value = z; } t->lazy = true; } T get_value(node* t){ if(t==NULL) return default_value; if(t->lazy) return T(t->value.c , (t->value.val + (t->lazy_value * t->value.c)) % MOD); return t->value; } vector v; node* root; int size; node* constract(node* t, int pos, int lb, int ub){ if(pos == 0){ t->par = t; } t->lb = lb; t->ub = ub; if(poslch = constract(&v[(pos<<1) + 1], (pos<<1) + 1, lb, (ub+lb)>>1); t->lch->par = t; t->rch = constract(&v[(pos<<1) + 2], (pos<<1) + 2, (ub+lb)>>1, ub); t->rch->par = t; } return t; } void initialize(int size_){ size = 1; while(size < size_) size <<= 1; v = vector(size<<1, node(default_value, default_lazy_value)); root = constract(&v[0], 0, 0, size); } //propagate lazy value of node t to its children void push(node* t){ if(t==NULL) return; if(t->lazy){ if(t->lch != NULL){ //has child new_lazy(t->lch, t->lazy_value); new_lazy(t->rch, t->lazy_value); t->value = evaluate( get_value(t->lch), get_value(t->rch) ); }else{ t->value = get_value(t); } t->lazy_value = default_lazy_value; t->lazy = false; } } void range_add(int left, int right, V z, node* t){ if(t==NULL) return; if(t->ub <= left || right <= t->lb){ return; } push(t); if(left <= t->lb && t->ub <= right){ new_lazy(t, z); return; } //partialy covered range_add(left, right, z, t->lch); range_add(left, right, z, t->rch); t->value = evaluate( get_value(t->lch), get_value(t->rch) ); } //get value of [left,right) T get_range_value(int left, int right, node* t){ if(t==NULL) return default_value; if(t->ub <= left || right <= t->lb){ return default_value; } push(t); if(left <= t->lb && t->ub <= right){ return get_value(t); } T L = get_range_value(left, right, t->lch); T R = get_range_value(left, right, t->rch); return evaluate(L, R); } public: //default node value must be set // sum : 0 // max : MIN_INF // min : MAX_INF // gcd : 1 Segment_Tree_Lazy(int size_) : default_value(T()), default_lazy_value(0LL){ initialize(size_); } Segment_Tree_Lazy() : default_value(T()), default_lazy_value(0LL){ } void resize(int sz){ initialize(sz); } //node[pos] <= new_value void update(int pos, T new_value){ node* t = &v[pos + size-1]; t->value = new_value; while(t != root){ t = t->par; t->value = evaluate( get_value(t->lch), get_value(t->rch) ); } } //[l,r) += add_value void range_add(int left, int right, V z){ range_add(left, right, z, root); } //get value [left,right) T get_range_value(int left, int right){ return get_range_value(left, right, root); } void dbg(){ for(int i=0; i seg; int size; int root; decomposited_node(){} decomposited_node(int size_, int root_) : seg(size_), size(size_), root(root_){ } }; class info{ public: decomposited_node* node; int pos; info():node(NULL){} }; int sub_tree_dfs(int pos, int par){ parent[pos] = par; int ret = 1; for(int i=0; i> G; vector parent; vector sub_tree_size; vector information; vector> decomposited_tree; vector dec_nodes; LCA lca; HL_Decomposition(vector>& G, int root = 0) : n(G.size()), sub_tree_size(G.size()), information(G.size()), lca(G,root), parent(G.size()){ this->G = G; sub_tree_dfs(0,0); vector visit(n, false); queue head; head.push(0); while(head.size()){ int pos = head.front(); decomposited_tree.push_back({pos}); head.pop(); visit[pos] = true; while(true){ int max_size = 0; int next = -1; for(int i=0; i=0){ head.push(next); } max_size = sub_tree_size[to]; next = to; }else{ head.push(to); } } if(next < 0) break; decomposited_tree.back().push_back(next); visit[next] = true; pos = next; } } dec_nodes.resize(decomposited_tree.size()); for(int i=0; iseg.get_range_value(l, r).val; ret += query_get_val(parent[t->root], lca_, type); ret %= MOD; return ret; }else{ int l = information[lca_].pos; int r = information[pos].pos+1; if(type == 1) l += 1; return t->seg.get_range_value(l, r).val; } } long long query_get(int x, int y){ int lca_ = lca.get_lca(x,y); long long ret = 0; ret += query_get_val(x, lca_, 0); ret += query_get_val(y, lca_, 1); ret %= MOD; return ret; } void query_set_val(int pos, int lca_, int type, long long z){ decomposited_node* t = information[pos].node; if(t != information[lca_].node){ int l = 0; int r = information[pos].pos+1; t->seg.range_add(l, r, z); query_set_val(parent[t->root], lca_, type, z); }else{ int l = information[lca_].pos; int r = information[pos].pos+1; if(type == 1) l += 1; t->seg.range_add(l, r, z); } } void query_set(int x, int y, long long z){ int lca_ = lca.get_lca(x,y); query_set_val(x, lca_, 0, z); query_set_val(y, lca_, 1, z); } }; int main(){ int n; scanf("%d", &n); s.resize(n); c.resize(n); for(int i=0; i> G(n); for(int i=0; i