代碼短小精悍,理解費勁= =.
總結下思路:
首先將相連的邊存起來( insert ):
用數組模擬一個單向鏈表,因而每一條邊存兩次;
鏈表的節點代表一條邊,有兩個值:蘋果樹的下一分叉點 & 當前節點上連的上一條邊.
一條邊的"地址"就是當前分叉點的加入序號(因為是用數組模擬的,也就是下標尋址).***
由於每一個分叉點的編號(除1外)只是一個id,故使用list數組實現id尋址.list值為id分叉點對應的最末加入的一條邊的地址. ***這裡很繞= =b注意順序
tree[ list[ id ] ] 就是id分叉點最末加入的一條邊啦.
注意由於list是全局變量,自動初始化為全0,也就是第一條邊的next為0邊.
同一個id分叉點的不同邊之間是直接用鏈表的next尋址的;
不同id分叉點的邊是直接借助list數組用id尋址的(只找到最末那條邊~).
然後把每一個id打上時間戳( make ):
這裡當然也是id尋址.
用一個結構體數組存儲每一個id對應的[進入,退出]時間.本代碼選擇退出增一,進入不變.反之也可~
這個過程要模擬DFS.
簡單來說就是;
1 總是找當前節點的下一個節點,直到葉子節點;
2 到達葉子節點後,記錄時間戳,入值==出值,出值++;返回上一分叉;
3 檢查是否有下一條邊(即找下一節點),若有,遞歸返回步驟1.
若沒有,入值=最小入值**,出值=最大出值++**; 返回上一分叉; **由於遞歸,這裡的數值變化不容易看清楚.
調用時 make( 0, 1 ),因此最後執行到步驟3時就會完全退出.
下面就是建立一個滿的線段樹(初始時每個分叉都有一個蘋果).
詢問時,根據tab找到此id對應的區間.詢問即可.
更改時,單點異或 tab[ id ].r 就行了(因為是對應時間戳的出值).
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 110000
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
/**
除了知道1為根節點之外其他編號都只能認為是id,數字沒有指導意義.可得唯一解.
**/
int min(int a, int b)
{
return a + ((b-a) & ((b-a) >> 31));
}
struct branch{///樹枝是單向的
int next,node;
}tree[maxn<<1];//由樹枝組成的樹
struct Node{
int l,r;
}tab[maxn];//由節點組成的表
int cnt,sum;//樹枝計數
///sum是時間戳的游標
int list[maxn],seg[maxn<<2];//seg是線段樹,list是..?(下文)
inline void insert(int fro,int to)//插入一條樹枝
{
tree[cnt].node = to;///node指向目標節點的id
tree[cnt].next = list[fro];///最初list[0]是0,此後都是fro對應樹枝的下標
///而此樹枝的next存的是上一次遺留下來的tree下標,由此可以找到上一條由fro引出的樹枝!!!
list[fro] = cnt++ ;//list是用id做index的..存的是tree下標
///看next的時候應該猜想"node"存的是節點id,而本身是樹枝,所以next應該是指向樹枝的指針
///而結構體的next是單向的指向下一節點,所以這裡的next也是單向的回溯,只不過是上一個樹枝
}
int make(int pre,int now)
{///l是進入時間戳,r是返回時間戳.這裡進入不計時間,返回才增
int p = list[now],mi = 2*maxn,t;///list指向最後一條邊
while(p){///list數組是初始化為0的,p==0說明已到達最後一條邊
t = tree[p].node;///t指向從now出發的下一節點
if(t!=pre)mi = min(make(now,t),mi);///對make總是傳入相鄰的節點參數
///這裡取min是為了一直保留進入時的時間戳,遞歸結束往回返的時候mi保留著,
///如果找到了下一個兒子,當且僅當每到一個葉子節點,mi會++
p = tree[p].next;///t==pre的話就停止遞歸,p==tree[p].next==0
///由於之前調用insert的時候,是連續(a,b)(b,a)的,所以,
///如果到達了"葉子樹枝"就會出現t==pre的狀況!!!
///當然,t!=pre的話遞歸完了也得走這裡往回退
///這個時候就是找下一個樹枝,繼續...SOGA!!這樣就模擬了DFS啊!!!= =b
}
mi = min(mi,sum);///退出的時候,葉子節點左右相等 均為sum.
///到達葉子節點時mi在這裡會變大!!!
tab[now].l = mi,tab[now].r = sum++;///tree和list的作用僅限於建時間戳
///到這裡,右端點總是++的,葉子節點的話就取mi(上面mi取了INF和sum的最小,是sum)
///不是葉子節點的話,就取實際的sum(兒子全部找完了退出的)
return mi;///返回mi,找兒子的時候mi是一樣的!
}
void update(int p,int l,int r,int rt)
{
if(l==r){//XOR 1
seg[rt] ^= 1 ;
return ;
}
int m = (l+r) >> 1;
if(p<=m)update(p,lson);
else update(p,rson);
seg[rt] = seg[rt<<1] + seg[rt<<1|1];
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&R>=r)return seg[rt];
int m = (l+r) >> 1,ret = 0;
if(m>=L)ret += query(L,R,lson);
if(m<R)ret+= query(L,R,rson);
return ret;
}
void build(int l,int r,int rt)
{
if(l==r){
seg[rt] = 1;
return ;
}
int m = (l+r) >> 1;
build(lson),build(rson);
seg[rt] = seg[rt<<1] + seg[rt<<1|1];//PushUp(rt);
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
//if(n==0)continue;
int a,b;
sum = cnt = 1;
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
insert(a,b);
insert(b,a);
}
make(0,1);//功能應該是把一條條樹枝拼接起來,成為一顆蘋果樹,然後進行DFS遍歷,得到時間戳
build(1,n,1);//功能應該是建立線段樹,這個線段樹是標准求和線段樹,本身和蘋果樹沒啥關系
//只是通過蘋果樹的DFS遍歷給蘋果樹的每個節點打上時間戳,然後在蘋果樹中找應該查詢的區間
//update的時候就是在線段樹中單點替換了,因為區間的對應是不會變的
int m,t;
char s[2];
scanf("%d",&m);
while(m--){
scanf("%s%d",s,&t);
if(s[0]=='Q')printf("%d\n",query(tab[t].l,tab[t].r,1,n,1));
//線段樹seg是該段的蘋果數
//tab中存的是時間戳,tab是以id尋址的..
else {
update(tab[t].r,1,n,1);
}
}
}
return 0;
}
