【DFS序+单点修改区间求和】POJ 3321 Apple Tree
2024-08-31 13:56:11
【题意】
给一棵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 ;
}
最新文章
- 利用python合并两个文件
- Spring学习笔记(一)
- dhtmlxScheduler日程安排控件
- poj1753枚举
- 设计模式学习之抽象工厂(Abstract Factory,创建型模式)(3)
- [ThinkPHP]MVC模块和URL访问
- magento后台登陆被锁定 索引报错的解决:General error: 1205 Lock wait timeout
- 图形数据库、NOSQL和Neo4j
- 谷歌官方刷新组件SwipeRefreshLayout
- zzuli oj 1146 吃糖果
- (转)Java Ant build.xml详解
- AlgorithmsI Exercises: UnionFind
- gdb命令中attach使用
- RabbitMQ (五)主题(Topic)
- js实现reqire中的amd,cmd功能
- SpringBoot笔记十三:引入webjar资源和国际化处理
- 【原创】大数据基础之Flume(2)kudu sink
- FreeCAD源码初步了解
- vue 局部引入js插件
- rhel7的xfs与Oracle database
热门文章
- SVN的两种存储方式FSFS和BDB比较【转】
- Azure CLI 2.0-Azure新命令行工具介绍
- MDI和在TabPage
- Maven项目报错:Failed to execute goal org.apache.maven.plugins:maven-clean-plugin:2.5:clean (default-clea
- Educational Codeforces Round 12补题 经典题 再次爆零
- 前端知识点总结——HTML
- myna代码
- python之道04
- iOS HmacSHA1加密 和 MD5 Base64加密 --iOS开发系列---项目中成长的知识五
- C++系统学习之七:类