poj 3321 Apple Tree(树状数组+dfs)中等难度

本文主要是介绍poj 3321 Apple Tree(树状数组+dfs)中等难度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、http://poj.org/problem?id=3321

2、题目大意：

有一棵树，有n个叉，由n-1条枝条连接，每个叉上最多有一个苹果，假设原来每个叉上都有苹果，现在要对这棵苹果树进行m个操作，其中这m个操作由两种操作组成，C x表示如果x点有苹果就摘掉，没有苹果就长一个，Q x是查询以x结点为根的树有多少个苹果，这道题目看上去好像是普通的树状数组的题目，但是没有顺序，我们需要先按照根搜索一遍，确定每棵子树的起始点和结束点，这样就可以转换成树状数组的题目了，

这道题目有个问题，用vector建树会超时，需要静态建树

3、题目：

Description

Input

Output

Sample Input

3
1 2
1 3
3
Q 1
C 2
Q 1

Sample Output

3
2

Source

 

4、Ac代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 100005
int s[N];
int e[N];
int cnt,n,edge=0;
int visit[N];
int c[N];
int v[N],next[N],head[N];
void add(int x,int y)
{v[edge]=y;next[edge]=head[x];head[x]=edge++;
}
void dfs(int u)
{s[u]=++cnt;for(int i=head[u];i!=-1;i=next[i]){int vv=v[i];dfs(vv);}e[u]=cnt;
}
int lowbit(int i)
{return i&(-i);
}
void update(int x,int v)
{for(int i=x; i<=n; i+=lowbit(i)){c[i]+=v;}
}
int getsum(int x)
{int sum=0;for(int i=x; i>0; i-=lowbit(i)){sum+=c[i];}return sum;
}
int main()
{int a,b,m;char ch[3];while(scanf("%d",&n)!=EOF){cnt=0;edge=0;memset(head,-1,sizeof(head));memset(c,0,sizeof(c));memset(visit,0,sizeof(visit));for(int i=1;i<=n;i++){update(i,1);}for(int i=1;i<n;i++){scanf("%d%d",&a,&b);add(a,b);}dfs(1);scanf("%d",&m);for(int i=1; i<=m; i++){scanf("%s%d",ch,&a);if(ch[0]=='Q'){int ans=getsum(e[a])-getsum(s[a]-1);printf("%d\n",ans);}else if(ch[0]=='C'){int v=s[a];if(visit[v]==1){update(v,1);visit[v]=0;}else{update(v,-1);visit[v]=1;}}}}return 0;
}
/*
3
1 2
1 3
3
Q 1
C 2
Q 3
3
1 2
1 3
3
Q 1
C 2
Q 1*/

 

链表建树的超时代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#include<vector>
#define N 100005
vector<int> adj[N];
int s[N];
int e[N];
int cnt,n;
int visit[N];
int c[N];
void dfs(int v,int f)
{//printf("v=%d\n",v);s[v]=++cnt;for(int i=0; i<adj[v].size(); i++){int vv=adj[v][i];if(vv!=f)dfs(vv,v);}e[v]=cnt;return ;
}
int lowbit(int i)
{return i&(-i);
}
void update(int x,int v)
{for(int i=x; i<=n; i+=lowbit(i)){c[i]+=v;}
}
int getsum(int x)
{int sum=0;for(int i=x; i>0; i-=lowbit(i)){sum+=c[i];// printf("i=%d %d %d\n",i,c[i],sum);}return sum;
}
int main()
{int a,b,m;char ch[3];while(scanf("%d",&n)!=EOF){cnt=0;memset(c,0,sizeof(c));memset(visit,0,sizeof(visit));for(int i=0;i<=n;i++)adj[i].clear();for(int i=1; i<n; i++){scanf("%d%d",&a,&b);//printf("ab=%d %d \n",a,b);adj[a].push_back(b);adj[b].push_back(a);}memset(s,0,sizeof(s));memset(e,0,sizeof(e));dfs(1,-1);scanf("%d",&m);for(int i=1; i<=n; i++){update(i,1);}for(int i=1; i<=m; i++){scanf("%s%d",ch,&a);if(ch[0]=='Q'){//printf("a=%d\n",a);int ans=getsum(e[a])-getsum(s[a]-1);printf("%d\n",ans);}else if(ch[0]=='C'){int v=s[a];if(visit[v]==1){update(v,1);visit[v]=0;}else{update(v,-1);visit[v]=1;}}}}return 0;
}

 

这篇关于poj 3321 Apple Tree(树状数组+dfs)中等难度的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---