1228 蘋果樹

?

?時間限制: 1 s ?空間限制: 128000 KB ?題目等級 : 鉆石 Diamond 題目描述?Description

在卡卡的房子外面，有一棵蘋果樹。每年的春天，樹上總會結出很多的蘋果。卡卡非常喜歡吃蘋果，所以他一直都精心的呵護這棵蘋果樹。我們知道樹是有很多分叉點的，蘋果會長在枝條的分叉點上面，且不會有兩個蘋果結在一起。卡卡很想知道一個分叉點所代表的子樹上所結的蘋果的數目，以便研究蘋果樹哪些枝條的結果能力比較強。

卡卡所知道的是，每隔一些時間，某些分叉點上會結出一些蘋果，但是卡卡所不知道的是，總會有一些調皮的小孩來樹上摘走一些蘋果。

于是我們定義兩種操作：

C?x	表示編號為x的分叉點的狀態被改變(原來有蘋果的話，就被摘掉，原來沒有的話，就結出一個蘋果)
G?x	查詢編號為x的分叉點所代表的子樹中有多少個蘋果

我們假定一開始的時候，樹上全都是蘋果，也包括作為根結點的分叉1。

輸入描述?Input Description

第一行一個數N?(n<=100000)

接下來n-1行,每行2個數u,v,表示分叉點u和分叉點v是直接相連的。

再接下來一行一個數M,(M<=100000)表示詢問數

接下來M行,表示詢問,詢問的格式如題目所述Q?x或者C?x

輸出描述?Output Description

對于每個Q?x的詢問,請輸出相應的結果,每行輸出一個

樣例輸入?Sample Input

3

1?2

1?3

3

Q?1

C?2

Q?1

樣例輸出?Sample Output

3

2

/* 這個題是一棵樹 他的點的編號順序并不是按照線段樹的節點順序來排列的 所以我們要想方設法把這個節點融入線段樹中 如何融入線段樹呢？ 首先把這些點和邊都存起來 然后我們考慮把節點存成一個線性的區間 所以是Dfs許 維護遍歷到的時間和結束的時間，形成一個區間。 然后每個節點就是就是它的區間的第一個值 線段樹完成單點修改和區間查詢 */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 100010using namespace std; int n,m,x,y,z,cnt,tot,time1[maxn],time2[maxn]; int head[maxn],vis[maxn]; char c;struct node0 {int from,to,dis,next; }e[maxn*2];struct node {int l,r,dis,flag; }tre[maxn*4];void add(int from,int to) {e[++cnt].from=from;e[cnt].to=to;e[cnt].next=head[from];head[from]=cnt; }void build(int now,int l,int r) {tre[now].l=l;tre[now].r=r;if(l==r){tre[now].dis=1;return;}int mid=(l+r)>>1;build(now<<1,l,mid);build(now<<1|1,mid+1,r);tre[now].dis=tre[now<<1].dis+tre[now<<1|1].dis; }void Dfs(int z) {time1[z]=++tot;vis[z]=1;for(int i=head[z];i;i=e[i].next){int v=e[i].to;if(!vis[v])Dfs(v);}time2[z]=tot; }void f_change(int now,int k) {int l=tre[now].l,r=tre[now].r;if(l==r){if(!tre[now].dis) tre[now].dis=1;else tre[now].dis=0;return;}int mid=(l+r)>>1;if(k>mid) f_change(now<<1|1,k);if(k<=mid) f_change(now<<1,k);tre[now].dis=tre[now<<1].dis+tre[now<<1|1].dis; }int Query(int now,int l,int r) {if(tre[now].l==l&&tre[now].r==r){return tre[now].dis;}tre[now].dis=tre[now<<1].dis+tre[now<<1|1].dis;int mid=(tre[now].l+tre[now].r)>>1;if(r<=mid)return Query(now<<1,l,r);else if(l>mid)return Query(now<<1|1,l,r);else{return Query(now<<1,l,mid)+Query(now<<1|1,mid+1,r);} }int main() {scanf("%d",&n);build(1,1,n);for(int i=1;i<n;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);}Dfs(1);scanf("%d",&m);for(int i=1;i<=m;i++){cin>>c>>z;if(c=='Q') printf("%d\n",Query(1,time1[z],time2[z]));if(c=='C') f_change(1,time1[z]);}return 0; } 心若向陽，無言悲傷

?

轉載于:https://www.cnblogs.com/L-Memory/p/6298280.html

總結

以上是生活随笔為你收集整理的苹果树（线段树+Dfs序）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。