首页 > 代码库 > 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-苹果树