poj.org/problem?id=3321

【题意】

给一棵n个节点的树,每个节点开始有一个苹果,m次操作
1.将某个结点的苹果数异或 1
2.查询一棵子树内的苹果数
 #include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll; const int maxn=1e5+;
const int maxm=*maxn;
int n;
struct edge
{
int to;
int nxt;
}e[maxm];
int head[maxn];
int tot;
int l[maxn],r[maxn];
int tree[maxm];
bool vis[maxn];
int cid;
int lowbit(int x)
{
return x&(-x);
} void add(int k,int x)
{
while(k<=cid)//注意是cid,不是n
{
tree[k]+=x;
k+=lowbit(k);
}
} int query(int k)
{
int ans=;
while(k)
{
ans+=tree[k];
k-=lowbit(k);
}
return ans;
}
void init()
{
memset(head,-,sizeof(head));
tot=;
cid=;
memset(vis,false,sizeof(vis));
} void addedge(int u,int v)
{
e[tot].to=v;
e[tot].nxt=head[u];
head[u]=tot++;
} void dfs(int u,int pa)
{
l[u]=++cid;
for(int i=head[u];i!=-;i=e[i].nxt)
{
int v=e[i].to;
if(v==pa) continue;
dfs(v,u);
}
r[u]=++cid;
} int main()
{
while(~scanf("%d",&n))
{
init();
int u,v;
for(int i=;i<=n-;i++)
{
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
dfs(,-);
for(int i=;i<=n;i++)
{
add(l[i],);//单点修改
}
int q;
scanf("%d",&q);
char str[];
int x;
while(q--)
{
scanf("%s%d",str,&x);
if(str[]=='Q')
{
int ans=query(r[x])-query(l[x]-);
printf("%d\n",ans);
}
else
{
if(!vis[x])
{
add(l[x],-);
vis[x]=true;
}
else
{
add(l[x],);
vis[x]=false;
}
}
}
}
return ;
}

最新文章

  1. 利用python合并两个文件
  2. Spring学习笔记(一)
  3. dhtmlxScheduler日程安排控件
  4. poj1753枚举
  5. 设计模式学习之抽象工厂(Abstract Factory,创建型模式)(3)
  6. [ThinkPHP]MVC模块和URL访问
  7. magento后台登陆被锁定 索引报错的解决:General error: 1205 Lock wait timeout
  8. 图形数据库、NOSQL和Neo4j
  9. 谷歌官方刷新组件SwipeRefreshLayout
  10. zzuli oj 1146 吃糖果
  11. (转)Java Ant build.xml详解
  12. AlgorithmsI Exercises: UnionFind
  13. gdb命令中attach使用
  14. RabbitMQ (五)主题(Topic)
  15. js实现reqire中的amd,cmd功能
  16. SpringBoot笔记十三:引入webjar资源和国际化处理
  17. 【原创】大数据基础之Flume(2)kudu sink
  18. FreeCAD源码初步了解
  19. vue 局部引入js插件
  20. rhel7的xfs与Oracle database

热门文章

  1. SVN的两种存储方式FSFS和BDB比较【转】
  2. Azure CLI 2.0-Azure新命令行工具介绍
  3. MDI和在TabPage
  4. Maven项目报错:Failed to execute goal org.apache.maven.plugins:maven-clean-plugin:2.5:clean (default-clea
  5. Educational Codeforces Round 12补题 经典题 再次爆零
  6. 前端知识点总结——HTML
  7. myna代码
  8. python之道04
  9. iOS HmacSHA1加密 和 MD5 Base64加密 --iOS开发系列---项目中成长的知识五
  10. C++系统学习之七:类