首页 > 代码库 > CodeVS-苹果树
CodeVS-苹果树
好久没写博客了,也好久没刷cv了,随便写篇烂文暖暖手吧...
这题是一道树上的题目...求和一般我们会想到树状数组或者线段树(蓝鹅暴力我也兹瓷,只是觉得这时间好像会爆
一开始看题没看仔细-->以为根节点不是1然后就开始烦恼,以为求一波重心(大雾
重心的求法听czl讲过,然后zzs说要用到什么点分治边分治(没学,不懂,难打,弃坑
因为qzz过了这道题,所以开始抱大腿-->树根是1啊...(论不看题。。。
于是知道了树根我就直接想着用dfs序转一下然后裸树状数组(没想到过了。。。
大概这样...跑的还挺快的>_<
#include<cstdio>#include<cmath>#include<cstring>#include<iostream>#include<vector>#include<map>#include<algorithm>using namespace std;#define maxn 100010#define ll long long#define rep(i,l,r,step) for(int i=l;i<=r;i+=step)#define down(i,l,r,step) for(int i=l;i>=r;i-=step)int n,q,t[maxn],l[maxn],r[maxn],cnt; bool f[maxn];//tree_array#define lowbit(x) x&-xint add(int x,int c){ rep(i,x,n,lowbit(i)) t[i]+=c;}int sum(int x){ int ans=0; down(i,x,1,lowbit(i)) ans+=t[i]; return ans;}int edge,to[maxn*2],next[maxn*2],head[maxn];//邻接表void insert(int u,int v){ to[++edge]=v; next[edge]=head[u]; head[u]=edge;} //dfs序void dfs(int rt,int fa){ l[rt]=++cnt; add(l[rt],1); for(int i=head[rt];i;i=next[i]){ if(to[i]!=fa) dfs(to[i],rt); } r[rt]=cnt;} int main(){ memset(f,1,sizeof(f)); scanf("%d",&n); rep(i,1,n-1,1){ int x,y; scanf("%d%d",&x,&y); insert(x,y); insert(y,x); } dfs(1,0); scanf("%d",&q); while(q--){ char op[10];int x; scanf("%s%d",op,&x); if(op[0]==‘Q‘) printf("%d\n",sum(r[x])-sum(l[x]-1)); else{ if(f[x]){ f[x]=0;add(l[x],-1); } else{ f[x]=1;add(l[x],1); } } } return 0;}
CodeVS-苹果树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。