Description

你家門前種了一棵蘋果樹，每年秋天，樹上都結滿了蘋果，你非常喜歡吃蘋果，所以一直精心照料著蘋果樹。 蘋果樹有N個分叉，分叉之間由枝干相連，你把分叉用1到N來標記，樹根必須記為1。蘋果長在分叉處，而且一個分叉最多只能同時結一個蘋果，也就是說不可能有超過一個蘋果同時長在分叉處。你想知道某個子樹中一共有多少個蘋果。 上面的問題不難，但現在的問題是有時你會去摘蘋果，有時又長出新的蘋果，那你還能做嗎？

Input

輸入文件第一行是一個整數N(N<=100000),表示樹中分叉的數目。 接下來N-1行每行兩個整數u和v，表示分叉u和分叉v有一個枝干相連。 下一行是一個整數M(M<=100000) 接下來M行，每行或者是“C x”表示x分叉處的狀態發生改變，如果原來有，就被摘下來，原來沒有就長出新的蘋果；或者是“Q x”表示詢問以分叉x為根的子樹中蘋果的數量。 注意起初每個分叉都有一個蘋果。

Output

對于每個詢問輸出對應的數量。

Sample Input

3
1 2
1 3
3
Q 1
C 2
Q 1

Sample Output

3
2

Sulotion

• 這題是一道典型的線段樹，需要單點修改和區間求和。

• 但一眼看去，貌似不知道區間的左右端點

• 但其實在DFS的時候就可以將點處理標號，一個點的子樹的標號一定是連續的，

• 那么對于一個點，存住它子樹所在的區間，即可進行線段樹操作。

Code

#include<cstdio> using namespace std; const int N=100001; int tot; int first[N],next[N<<1],en[N<<1]; int mx[N],g[N],f[N<<2]; inline int read() {int X=0; char ch=0;while(ch<'0' || ch>'9') ch=getchar();while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X; } inline void insert(int x,int y) {next[++tot]=first[x];first[x]=tot;en[tot]=y; } inline void dfs(int x,int y) {mx[x]=g[x]=++tot;for(int i=first[x];i;i=next[i])if(en[i]!=y){dfs(en[i],x);mx[x]=mx[en[i]];} } inline void make(int v,int l,int r) {if(l==r){f[v]=1;return;}int mid=(l+r)>>1;make(v<<1,l,mid);make(v<<1|1,mid+1,r);f[v]=f[v<<1]+f[v<<1|1]; } inline void change(int v,int l,int r,int x) {if(l==r){f[v]=f[v]^1;return;}int mid=(l+r)>>1;if(x<=mid) change(v<<1,l,mid,x); else change(v<<1|1,mid+1,r,x);f[v]=f[v<<1]+f[v<<1|1]; } inline int query(int v,int l,int r,int x,int y) {if(l==x && r==y) return f[v];int mid=(l+r)>>1;if(y<=mid) return query(v<<1,l,mid,x,y);if(x>mid) return query(v<<1|1,mid+1,r,x,y);return query(v<<1,l,mid,x,mid)+query(v<<1|1,mid+1,r,mid+1,y); } int main() {int n=read();for(int i=1;i<n;i++){int x=read(),y=read();insert(x,y);insert(y,x);}dfs(1,tot=0);make(1,1,n);int m=read();while(m--){char ch=getchar();while(ch!='Q' && ch!='C') ch=getchar();int x=read();if(ch=='C') change(1,1,n,g[x]); elseprintf("%d\n",query(1,1,n,g[x],mx[x]));}return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 1016. 【PKU3321】苹果树的全部內容，希望文章能夠幫你解決所遇到的問題。

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