Index: lib/dataStructure/segmentTree.cpp
==================================================================
--- lib/dataStructure/segmentTree.cpp
+++ lib/dataStructure/segmentTree.cpp
@@ -1,17 +1,46 @@
 //-------------------------------------------------------------
 // Segment tree
 //   in some general form
 //
 // Verified by
-//   - Codeforces 107 C
-//   - Codeforces 104 E
+//   - Codeforces 200 D
+//   - Codeforces 107 C (old version)
+//   - Codeforces 104 E (old version)
 //-------------------------------------------------------------
 
-template<typename Node>
 class SegmentTree
 {
+	struct Node
+	{
+		int sum;
+
+		static Node Zero()
+		{
+			Node c = {0};
+			return c;
+		}
+		static Node One(int v)
+		{
+			Node c = {v};
+			return c;
+		}
+		static Node Concat(const Node& l, const Node& r)
+		{
+			Node c = {l.sum + r.sum};
+			return c;
+		}
+		static Node Repeat(const Node& n, int k)
+		{
+			if(k==0) return Zero();
+			Node c = {n.sum * k};
+			return c;
+		}
+
+		bool lazy;
+	};
+
 public:
 	template<typename Seq>
 	SegmentTree(const Seq& s) {
 		int N = 1;
 		while( N < s.size() )
@@ -31,26 +60,23 @@
 	Node Query(int s, int e) { // compute h( seq[s,e) ) :  O(log n)
 		return QueryRec(s, e, tree.size()-1, 0, tree[0].size());
 	}
 
 	template<typename Value>
-	void Set(int s, int e, Value v) { // seq[s,e):=v : O(log n |e-s|)
+	void Set(int s, int e, Value v) { // seq[s,e):=v : O(log n)
 		SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size());
 	}
 
 private:
-	void CalcMidNode(int lv, int idx)
-	{
-		tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2+1]);
-	}
-
 	Node QueryRec(int s, int e, int lv, int idx, int stride)
 	{
 		const int myL = stride*idx;
 		const int myR = stride*(idx+1);
 		if( e<=myL || myR<=s )
 			return Node::Zero();
+		ResolveLazy(lv, idx);
+
 		if( s<=myL && myR<=e )
 			return tree[lv][idx];
 		return Node::Concat(QueryRec(s,e,lv-1,idx*2,stride/2),
 		                    QueryRec(s,e,lv-1,idx*2+1,stride/2));
 	}
@@ -59,149 +85,40 @@
 	{
 		const int myL = stride*idx;
 		const int myR = stride*(idx+1);
 		if( e<=myL || myR<=s )
 			return;
+		ResolveLazy(lv, idx);
+
 		if( stride == 1 ) {
 			tree[lv][idx] = n;
 		} else {
+			if( s<=myL && myR<=e ) {
+				tree[lv][idx] = n;
+				tree[lv][idx].lazy = true;
+				ResolveLazy(lv, idx);
+				return;
+			}
 			SetRec(s,e,n,lv-1,idx*2,stride/2);
 			SetRec(s,e,n,lv-1,idx*2+1,stride/2);
 			CalcMidNode(lv, idx);
 		}
 	}
 
-	vector< vector<Node> > tree;
-};
+	void CalcMidNode(int lv, int idx)
+	{
+		tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2+1]);
+	}
 
-struct Node
-{
-	double sum;
-	double maxLeft;
-	double maxRight;
-	double maxSum;
-	static Node Zero()
+	void ResolveLazy(int lv, int idx)
 	{
-		Node c = {0, 0, 0, 0};
-		return c;
-	}
-	static Node One(double v)
-	{
-		Node c = {v, max(0.0,v), max(0.0,v), max(0.0,v)};
-		return c;
-	}
-	static Node Concat(const Node& l, const Node& r)
-	{
-		Node c = {
-			l.sum + r.sum,
-			max(l.maxLeft, l.sum+r.maxLeft),
-			max(l.maxRight+r.sum, r.maxRight),
-			max(max(l.maxSum, r.maxSum), l.maxRight+r.maxLeft),
-		};
-		return c;
-	}
-};
-
-/*
-class SegmentTree
-{
-	// --- DATA FOR EACH NODE ---
-	struct Node
-	{
-		int sum;
-		int maxLeft;
-		int minLeft;
-		int n4;
-		int n7;
-		bool switched;
-	};
-	// --- DATA FOR EACH NODE ---
-
-	Node Canonical(int lv, int idx)
-	{
-		Node& x = tree[lv][idx];
-		// --- DO SOMETHING IF YOU NEED CANONICALIZATION ---
-		if( !x.switched )
-			return x;
-		Node n = {-x.sum, -x.minLeft, -x.maxLeft, x.n7, x.n4, false};
-		return n;
-		// --- DO SOMETHING IF YOU NEED CANONICALIZATION ---
-	}
-
-	void UpdateMidNode(int lv, int idx)
-	{
-		Node l = Canonical(lv-1, idx*2);
-		Node r = Canonical(lv-1, idx*2+1);
-		// --- BOTTOM UP COMPUTATION ---
-		Node me = {
-			l.sum + r.sum,
-			max(l.maxLeft, l.sum+r.maxLeft),
-			min(l.minLeft, l.sum+r.minLeft),
-			l.n4 + r.n4,
-			l.n7 + r.n7,
-			false
-		};
-		// --- BOTTOM UP COMPUTATION ---
-		tree[lv][idx] = me;
+		if(tree[lv][idx].lazy) {
+			if(lv > 0) {
+				tree[lv-1][idx*2]   = tree[lv][idx];
+				tree[lv-1][idx*2+1] = tree[lv][idx];
+			}
+			tree[lv][idx] = Node::Repeat(tree[lv][idx], 1<<lv);
+		}
 	}
 
 	vector< vector<Node> > tree;
-
-public:
-	SegmentTree(const string& s)
-	{
-		int N = 1;
-		while( N < s.size() )
-			N <<= 1;
-
-		tree.resize(tree.size()+1); tree.back().resize(N);
-		for(int i=0; i<N; ++i)
-		{
-			// --- INITIALIZE BASE 1-ELEMENT NODES ---
-			int v = i<s.size() ? (s[i]=='4' ? +1 : -1) : 0;
-			Node me = {v, max(0,v), min(0,v), v==+1, v==-1, false};
-			// --- INITIALIZE BASE 1-ELEMENT NODES ---
-			tree.back()[i] = me;
-		}
-
-		while(N>>=1)
-		{
-			tree.resize(tree.size()+1); tree.back().resize(N);
-			for(int i=0; i<N; ++i)
-				UpdateMidNode(tree.size()-1, i);
-		}
-	}
-
-	int Count()
-	{
-		Node x = Canonical(tree.size()-1, 0);
-		return x.maxLeft + x.n7;
-	}
-
-	void Switch(int L, int R)
-	{
-		SwitchRec(tree[0].size(), tree.size()-1, 0, L, R);
-	}
-
-	void SwitchRec(int Stride, int lv, int idx, int Raw_L, int Raw_R)
-	{
-		// Outside
-		if( Raw_R <= Stride*idx || Stride*(idx+1) <= Raw_L )
-			return;
-
-		// Inside
-		bool& me = tree[lv][idx].switched;
-		if( Raw_L <= Stride*idx && Stride*(idx+1) <= Raw_R )
-		{
-			me ^= 1;
-			return;
-		}
-
-		// Overlap
-		tree[lv-1][idx*2].switched   ^= me;
-		tree[lv-1][idx*2+1].switched ^= me;
-		SwitchRec(Stride/2, lv-1, idx*2,   Raw_L, Raw_R);
-		SwitchRec(Stride/2, lv-1, idx*2+1, Raw_L, Raw_R);
-		UpdateMidNode(lv, idx);
-	}
 };
-*/

ADDED   lib/graph/treeDfsNumbering.cpp
Index: lib/graph/treeDfsNumbering.cpp
==================================================================
--- lib/graph/treeDfsNumbering.cpp
+++ lib/graph/treeDfsNumbering.cpp
@@ -0,0 +1,42 @@
+//-------------------------------------------------------------
+// Tree DFS numbering
+//   O(N)
+//
+// G : adjacent list of a graph (forming a tree)
+// Labels each node v as dfs[v].
+// Inclusive [dfs[v], dfs_end[v]] denotes the descendant range.
+//
+// Verified by
+//   - Codeforces 200 Div1 D
+//-------------------------------------------------------------
+
+void dfs_numbering(
+	int root,
+	const vector<vector<int>>& G, vector<int>& dfs, vector<int>& dfs_end,
+	vector<int>& parent_of)
+{
+	int dfs_number = root;
+	dfs[root] = dfs_number++;
+	parent_of[root] = -1;
+
+	stack<tuple<int,int,int>> stk;
+	stk.push(make_tuple(-1, root, 0));
+	while(!stk.empty()) {
+		int grandparent = get<0>(stk.top());
+		int parent      = get<1>(stk.top());
+		int child_id    = get<2>(stk.top());
+		stk.pop();
+		if(G[parent].size() <= child_id) {
+			dfs_end[parent] = dfs_number - 1;
+			continue;
+		}
+		stk.push(make_tuple(grandparent, parent, child_id+1));
+
+		int me = G[parent][child_id];
+		if(me != grandparent) {
+			dfs[me] = dfs_number++;
+			parent_of[me] = parent;
+			stk.push(make_tuple(parent, me, 0));
+		}
+	}
+}