[BZOJ]1103: [POI2007]大都市meg

Description

在經濟全球化浪潮的影響下,習慣於漫步在清晨的鄉間小路的郵遞員Blue Mary也開始騎著摩托車傳遞郵件了。不過，她經常回憶起以前在鄉間漫步的情景。昔日，鄉下有依次編號為1..n的n個小村莊，某些村莊之間有一些雙向的土路。從每個村莊都恰好有一條路徑到達村莊1（即比特堡）。並且，對於每個村莊，它到比特堡的路徑恰好只經過編號比它的編號小的村莊。另外，對於所有道路而言，它們都不在除村莊以外的其他地點相遇。在這個未開化的地方，從來沒有過高架橋和地下鐵道。隨著時間的推移，越來越多的土路被改造成了公路。至今，Blue Mary還清晰地記得最後一條土路被改造為公路的情景。現在，這裡已經沒有土路了——所有的路都成為了公路，而昔日的村莊已經變成了一個大都市。 Blue Mary想起了在改造期間她送信的經歷。她從比特堡出發，需要去某個村莊，並且在兩次送信經歷的間隔期間,有某些土路被改造成了公路.現在Blue Mary需要你的幫助：計算出每次送信她需要走過的土路數目。（對於公路，她可以騎摩托車；而對於土路，她就只好推車了。）

Input

第一行是一個數n(1 < = n < = 2 50000).
以下n-1行，每行兩個整數a，b（1 < = a以下一行包含一個整數m（1 < = m < = 2 50000），表示Blue Mary曾經在改造期間送過m次信。
以下n+m-1行，每行有兩種格式的若干信息，表示按時間先後發生過的n+m-1次事件:
若這行為 A a b(a若這行為 W a, 則表示Blue Mary曾經從比特堡送信到村莊a。

Output

有m行，每行包含一個整數，表示對應的某次送信時經過的土路數目。

Sample Input

Sample Output

HINT

這是我做的第二道有關DFS序，BFS序的題了。這種題說難不難，說簡單不簡單，重在對於看出問題的本質，分析出究竟改變了什麼，怎麼改變了，改變量有什麼特點。

這題抽象一下，最先每個點的值存的是到1的距離，也就是深度，然後給出m個操作，操作有兩種：1.詢問一個點的值；2.將一個點及他的子樹的值全部減1。

我們發現，我們每次操作，是想盡量快的更改他和他的子樹，那麼自然他和他的子樹放在一起更好改，於是可以想到DFS序，對於一棵樹的DFS序，一個節點的兒子一定是在一個區間內的，那麼只要我們記下這個區間在哪兒，每次就可以想怎麼搞怎麼搞了。

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define MAX_N 300000
int n,m;
int tot;
int fir[MAX_N*2],en[MAX_N*2],nex[MAX_N*2];
void ins(int a,int b){
	nex[++tot]=fir[a];
	fir[a]=tot;
	en[tot]=b;
	
	nex[++tot]=fir[b];
	fir[b]=tot;
	en[tot]=a;
}
int top,sta[MAX_N*2];
int L[MAX_N],R[MAX_N],bel[MAX_N],dep[MAX_N];
void dfs(int now,int deep){
	sta[++top]=now;
	bel[now]=top;
	dep[now]=deep;
	L[now]=top+1;
	for (int k=fir[now];k;k=nex[k])
		if (!bel[en[k]])
			dfs(en[k],deep+1);
	R[now]=top;
	if (R[now]y) swap(x,y);
			modify(1,1,n,bel[y],bel[y]);
			if (!(L[y]==0||R[y]==0))modify(1,1,n,L[y],R[y]);
			}
		}
	
	
	return 0;
}