// 基本テンプレート #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++) #define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++) #define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--) #define debug(...) fprintf(stderr, __VA_ARGS__) #define int long long int template void chmax(T &a, T b) {a = max(a, b);} template void chmin(T &a, T b) {a = min(a, b);} template void chadd(T &a, T b) {a = a + b;} typedef pair pii; typedef long long ll; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; const ll INF = 1001001001001001LL; const ll MOD = 1000000007LL; // vector 版 (HL 分解に載せるときとかに使おう) template struct lazysegtree { // ノード、単位元 T I; vector node, lazy; vector need_upd; int SIZE; // オペレーション (update, query の 2 つが必要?) // update function は範囲を指定する形にしよう // upd_f(X, Y, l, r) -> 範囲が [l, r) であるようなノード X に Y を反映! // lazy について update するときは範囲を 1 にしないとバグります T (*upd_f)(T, T, int, int), (*qry_f)(T, T); // 演算子と単位元をセットし、全ての node と lazy を単位元で初期化 lazysegtree(int seg_size, T (*op1)(T, T, int, int), T (*op2)(T, T), T X) { upd_f = op1; qry_f = op2; I = X; SIZE = 1; while(SIZE < seg_size) SIZE *= 2; node = vector (2*SIZE, I ); lazy = vector (2*SIZE, I ); need_upd = vector(2*SIZE, false); } // 配列 vec の値で初期化 void init(vector vec) { int N = (int)vec.size(); for(int i=0; i=0; i--) { node[i] = qry_f(node[2*i+1], node[2*i+2]); } } void lazy_eval(int k, int l, int r) { if(!need_upd[k]) return; node[k] = upd_f(node[k], lazy[k], l, r); if(r - l > 1) { lazy[2*k+1] = upd_f(lazy[2*k+1], lazy[k], 0, 1); lazy[2*k+2] = upd_f(lazy[2*k+2], lazy[k], 0, 1); need_upd[2*k+1] = need_upd[2*k+2] = true; } lazy[k] = I; need_upd[k] = false; } // 半開区間 [a, b) に対して値 val を反映させる // (upd_f を用いて処理) void update(int a, int b, T val, int l=0, int r=-1, int k=0) { if(r < 0) r = SIZE; lazy_eval(k, l, r); if(b <= l || r <= a) return; if(a <= l && r <= b) { lazy[k] = upd_f(lazy[k], val, 0, 1); need_upd[k] = true; lazy_eval(k, l, r); } else { int mid = (l + r) / 2; update(a, b, val, l, mid, 2*k+1); update(a, b, val, mid, r, 2*k+2); node[k] = qry_f(node[2*k+1], node[2*k+2]); } } // 半開区間 [a, b) に対してクエリを投げる // (qry_f を用いて処理) T query(int a, int b, int l=0, int r=-1, int k=0) { if(r < 0) r = SIZE; lazy_eval(k, l, r); if(b <= l || r <= a) return I; if(a <= l && r <= b) return node[k]; int mid = (l + r) / 2; T vl = query(a, b, l, mid, 2*k+1); T vr = query(a, b, mid, r, 2*k+2); return qry_f(vl, vr); } }; // 移動元と行先と辺のコストを記録する構造体 template struct Edge { int from, to; T cost; Edge(int s, T d) : to(s), cost(d) {} Edge(int f, int s, T d) : from(f), to(s), cost(d) {} bool operator<(const Edge &e) const { return cost < e.cost; } bool operator>(const Edge &e) const { return cost > e.cost; } }; template using Graph = vector< vector< Edge > >; // HL 分解 // ある頂点 v の子たち c_i について、それを根とする部分木の頂点数が // 最大のものの 1 つを c_h とおく。このとき、辺 (v, c_h) は "heavy" な辺であるという。 // それ以外の辺は "light" な辺であるという。 // すべての辺を "heavy" と "light" に分類すると、木は "heavy" からなるパス // (下のコードだと chain) に分解 ("heavy" でつながっている頂点をひとつにまとめる) できる。 // これを HL 分解という。 // chain を縮約したあとの木の高さは O(log N) である。 // これは、"heavy" な辺の定義より、頂点 v と "light" な辺で結ばれている v の子それぞれに対して、 // 部分木の大きさが subsize(v) / 2 以下となっていることから導ける。 // "light" な辺を通るたびに部分木のサイズが半分以下になるため、深さは O(log N) となる。 template using Graph = vector< vector< Edge > >; template struct HLD { int N; const Graph G; // ・元の木について // 根からの深さ、自分の親、自分を根にしたときの部分木のサイズ // および、その頂点から出る "heavy" な辺 vector depth, parent, subsize, heavy; // ・chain について // chain の先頭要素、末尾要素、その頂点の 1 つ次・前の要素、chain 内でのインデックス vector head, last, prev, next, chain, idx; // chain の情報 (同じ vector 内にある要素どうしは同じ chain に属する) vector< vector > chains; // 各 chain に載せる遅延評価セグ木 (抽象) vector< lazysegtree > segs; HLD(const Graph &H, int r=-1) : N(H.size()), G(H), depth(N, -1), parent(N, 0), subsize(N, 0), heavy(N, -1), head(N), last(N), prev(N, -1), next(N, -1), chain(N, -1), idx(N, 0) { if(r != -1) decompose(r); } // root を根として分解 void decompose(const int root) { stack st; st.push(root); parent[root] = -1; depth[root] = 0; while(st.size()) { int cur_v = st.top(); st.pop(); // その頂点を初めて訪れた if(cur_v >= 0) { st.push(~cur_v); for(auto e : G[cur_v]) { // 親の方向でなければ値を更新 if(depth[e.to] != -1) continue; depth[e.to] = depth[cur_v] + 1; parent[e.to] = cur_v; st.push(e.to); } } // 帰りがけ else { int ma = 0; cur_v = ~cur_v; subsize[cur_v] = 1; for(auto e : G[cur_v]) { if(parent[cur_v] == e.to) continue; subsize[cur_v] += subsize[e.to]; if(ma < subsize[e.to]) { // cur_v と部分木のサイズが最大の子を結ぶ // (これが "heavy" の辺) ma = subsize[e.to]; heavy[cur_v] = e.to; } } } } st.push(root); while(st.size()) { int cur_v = st.top(); st.pop(); for(auto e : G[cur_v]) { if(parent[cur_v] != e.to) st.push(e.to); } // すでにその頂点について構築済みなら、何もしない // (chain の先頭の頂点でない) if(chain[cur_v] != -1) continue; chains.push_back(vector()); vector &path = chains.back(); // cur_v を始点として、heavy な辺をたどりながら下がる for(int v=cur_v; v!=-1; v=heavy[v]) { path.push_back(v); } for(size_t i=0; i(chains[i].size(), op1, op2, X)); } } // 頂点 v について、どの chain に属するか、 // またその chain の中でのインデックスは何かを pair で返す pair get_index(int v) { return make_pair(chain[v], idx[v]); } void debug_path() { for(size_t i=0; i G(N); for(int i=0; i(v, 1)); G[v].push_back(Edge(u, 1)); } HLD hl(G, 0); hl.buildSegtree(upd, fnd, 0); int Q; scanf("%lld", &Q); int ans = 0; for(int i=0; i