这两天比赛好多啊。当好不容易可以静下心来写一道题时却发现,树状数组是神马??忘光了诶~~~
这逗的不是一星半点啊,又看了好长时间。终于可以写这道题了!
题目大意:
给出N个点,N-1条边的无向图,处理成以一号节点为根的树。每个节点上有一个苹果。
有两种操作:
1、操作C:将给定节点的苹果状态修改,若有苹果就变为没有,若没有就变为有。
2、操作Q:输出以给定节点为根的子数上共有几个苹果。
解题思路:
这个题就是告诉我是用树状数组我也不会用啊~~
首先需要DFS处理图变为树,这个过程中需要记录每个节点的标号和它子树上节点的最大标号。在查询和修改的时候我们用都是这个类似于时间戳一样的标号。因为这样才能将根节点与子节点搭上关系
然后就是一维树状数组的正常查找,修改操作。
下面是代码:
#include <stdio.h> #include <string.h> int head[100005]; struct node1 { int to,next; }node[100005<<1]; int low[100005],high[100005],cnt,time=0,n; int num[100005]; bool vis[100005]; void addedge(int u,int v) { node[cnt].to=v; node[cnt].next=head[u]; head[u]=cnt++; } void dfs(int u) { time++; low[u]=time; int p=head[u]; while(p!=-1) { if(low[node[p].to]==0) dfs(node[p].to); p=node[p].next; } high[u]=time; } int lowbit(int k) { return k&(-k); } void add(int x,int val) { for(;x<=n;x+=lowbit(x)) { num[x]+=val; } } int query(int x) { int ans=0; for(;x>0;x-=lowbit(x)) { ans+=num[x]; } return ans; } int main() { int u,v,q; scanf("%d",&n); cnt=0; memset(head,-1,sizeof(head)); for(int i=0;i<n-1;i++) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } memset(low,0,sizeof(low)); dfs(1); memset(num,0,sizeof(num)); memset(vis,false,sizeof(vis)); for(int i=1;i<=n;i++) { add(i,1); } char s[3]; scanf("%d",&q); for(int i=0;i<q;i++) { scanf("%s",s); if(s[0]==‘C‘) { scanf("%d",&u); if(vis[low[u]]) { add(low[u],1); vis[low[u]]=false; } else { vis[low[u]]=true; add(low[u],-1); } } else if(s[0]==‘Q‘) { scanf("%d",&u); printf("%d\n",query(high[u])-query(low[u]-1)); } } return 0; }