主要是dfs,只要dfs這一步想到，也就是怎樣把問(wèn)題轉(zhuǎn)化為區(qū)間求和，就很容易用樹(shù)狀數(shù)組來(lái)求解

#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn= 100000; int head[maxn+10],e[maxn+10],num[maxn+10],lim[maxn+10],sumx[maxn+10],vis[maxn+10]; int nextx[maxn+10]; int n,m,tot,tem; void dfs(int x)//遍歷映射每個(gè)點(diǎn)，確定每個(gè)點(diǎn)的起始在他和終止的點(diǎn)，也就是每個(gè)蘋(píng)果和他這個(gè)子樹(shù)之上的最后一個(gè)節(jié)點(diǎn)映射后的編號(hào)。 {num[x]=tem++;int i;for(i=head[x];i!=-1;i=nextx[i]) dfs(e[i]);lim[x]=tem; } int lowbit(int x) {return x&(-x); } void update(int x) {int i,flag=0;if(vis[x]){vis[x]=0;flag=1;}else vis[x]=1;for(i=x;i<=maxn;i+=lowbit(i)){if(flag) sumx[i]-=1;else sumx[i]+=1;} } int query(int x) {int i,sum=0;for(i=x;i>0;i-=lowbit(i)) sum+=sumx[i];return sum; } int main() {while(cin>>n){int i;int u,v;tot=0;memset(head,-1,sizeof(head));memset(sumx,0,sizeof(sumx));memset(vis,0,sizeof(vis));for(i=0;i<n-1;i++)//先把圖建起來(lái){scanf("%d %d",&u,&v);e[tot]=v; nextx[tot]=head[u];head[u]=tot;tot++;}tem=1;dfs(1);scanf("%d",&m);for(i=1;i<tem;i++) update(num[i]);char c;for(i=0;i<m;i++){getchar();scanf("%c %d",&c,&v);if(c=='C') update(num[v]);else printf("%d\n",query(lim[v]-1)-query(num[v])+vis[num[v]]);}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/lj030/archive/2013/01/24/3002268.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的poj 3321的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。