Apple Tree poj-3321

　　　　題目大意：給你一個根固定的樹，每一個點的點權是0或1，查詢子樹點權和。

　　　　注釋：$1\le n \le 10^5$。

　　　　　　想法：剛剛學習dfs序，刷到水題偶哈哈。

　　　　　　　　什么是dfs序？就是在遍歷樹的時候記錄的每個點的出棧入棧序。這樣就可以保證每一個節會出現兩次且它的子樹被其夾在中間。

　　　　　　然后，子樹信息就可以通過維護序列的鬼東西維護了qwq。

　　　　　　緊接著，我們用樹狀數組維護被節點夾著的區間，就是端點節點的子樹，用樹狀數組更新即可。

　　　　最后，附上丑陋的代碼... ...

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define maxn 100010 using namespace std; int tot,cnt; int to[2*maxn],head[maxn],nxt[2*maxn]; int d[2*maxn]; int p1[maxn],p2[maxn]; int tree[4*maxn]; inline void add(int x,int y) {to[++tot]=y;nxt[tot]=head[x];head[x]=tot; } int lowbit(int x) {return x&(-x); } void dfs(int pos,int fa)//初始構造dfs序 {d[++cnt]=1;p1[pos]=cnt;for(int i=head[pos];i;i=nxt[i]){if(to[i]==fa) continue;dfs(to[i],pos);}p2[pos]=cnt; } void fix(int x,int ch) {for(int i=x;i<=cnt;i+=lowbit(i)){tree[i]+=ch;} } int query(int x) {int ans=0;for(int i=x;i;i-=lowbit(i)){ans+=tree[i];}return ans; } void original() {cnt=tot=0;memset(tree,0,sizeof tree);memset(head,0,sizeof head); } int main() {int n,m;while(~scanf("%d",&n)){original();for(int a,b,i=1;i<n;i++){scanf("%d%d",&a,&b);add(a,b);add(b,a);}dfs(1,0);for(int i=1;i<=n;i++)//別忘了建樹{fix(p1[i],1);}// for(int i=1;i<=cnt;i++)// {// printf("%d ",query(i));// }// puts("");char s[20];scanf("%d",&m);for(int x,i=1;i<=m;i++){scanf("%s",s+1);if(s[1]=='C'){scanf("%d",&x);if(d[p1[x]]==1) fix(p1[x],-1);else fix(p1[x],1);d[p1[x]]^=1;}else{scanf("%d",&x);printf("%d\n",query(p2[x])-query(p1[x]-1));}}}return 0; } // int main() // { // int n; // scanf("%d",&n); // for(int a,b,i=1;i<n;i++) // { // scanf("%d%d",&a,&b); // add(a,b); // add(b,a); // } // dfs(1,0); // for(int i=1;i<=cnt;i++) // { // printf("%d ",d[i]); // } // puts(""); // for(int i=1;i<=n;i++) // { // printf("%d %d\n",p1[i],p2[i]); // } // return 0; // }

?　　　　小結：dfs序好東西好東西... ...

轉載于:https://www.cnblogs.com/ShuraK/p/8710605.html

總結

以上是生活随笔為你收集整理的[poj3321]Apple Tree_dfs序_树状数组的全部內容，希望文章能夠幫你解決所遇到的問題。

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