首页 > 代码库 > cogs2039树的统计 x
cogs2039树的统计 x
2039. 树的统计
★★ 输入文件：counttree.in 输出文件：counttree.out 简单对比
时间限制：1 s 内存限制：128 MB
【题目描述】
关于树的统计问题有多种多样的版本，这里你需要解决一个比较简单的问题：对于一棵包含N个节点的有根树，将所有点从1到N编号后，对于每一个节点v，统计出以v为根的子树中有多少个点的编号比v小。
【输入格式】
输入第一行包含一个整数N，以下N行每行包含一个整数，其中第i行的整数表示编号为i的节点的父亲节点的编号，根的父亲节点编号为0。
【输出格式】
输出包含N行，其中第i行给出编号为i的节点的统计结果。
【样例输入】
3
2
3
0
【样例输出】
0 1 2
【提示】
在此键入。
【来源】
20%的数据1<=n<=1000
100%的数据1<=n<=100000
思路:
就是用搜索w
T代码:
#include <algorithm>#include <iostream>#include <cstring>#include <queue>#include <string>#include <cstdio> using namespace std; inline int reads(){ int x=0,f=1; char ch=getchar(); while(ch>‘9‘ || ch<‘0‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘ && ch<=‘9‘) { x=x*10+ch-‘0‘; ch=getchar(); } return x*f;} const int Ms = 1e5 + 2;int n,root;int dad[Ms];bool Vss[Ms];int sum[Ms];int deep[Ms];int h[Ms],num;queue<int>q; struct AC{ int to,next;}t[Ms]; void ADD(int x,int y){ t[++num].to=y; t[num].next=h[x]; h[x]=num;} int ans; void dfs(int u){ ///dfs the deep Vss[u]=true; int maxx=0; for(int j=h[u];j;j=t[j].next) { int v=t[j].to; if(Vss[v]) continue; deep[v]=deep[u]+1; ///update dad[v]=u; ///u is v‘s dad dfs(v); ///continue dfs if(sum[v] > sum[maxx]) maxx=v; ///update sum[u]+=sum[v]+1; }} void QwQ(int now){ ans=0; int nowdeep=deep[now]; for(int i=1;i<now;i++) {// if(i==now) continue; if(ans>=sum[now]) break; if(deep[i]>nowdeep && ans<=sum[now]) { if(dad[i]==now) ans++; else { int j=dad[i]; while(deep[j] > deep[now]) { j=dad[j]; if(j==now) ans++; } } } }} int main(){ freopen("counttree.in","r",stdin); freopen("counttree.out","w",stdout); n=reads(); int i=1; ///fu chu zhi !!! int QAQ; int sss=n; while(sss--) { ///i‘s dad is dad[i] QAQ=reads(); ADD(QAQ,i); ///find the root if(QAQ==0) root=i; i++; } deep[root]=1; sum[0]=-1; dfs(root); for(int i=1;i<=n;i++) { QwQ(i); printf("%d\n",ans); } return 0;}
A代码:
#include <algorithm>#include <iostream>#include <cstring>#include <queue>#include <string>#include <cstdio> using namespace std; inline int reads(){ int x=0,f=1; char ch=getchar(); while(ch>‘9‘ || ch<‘0‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘ && ch<=‘9‘) { x=x*10+ch-‘0‘; ch=getchar(); } return x*f;} const int Ms = 1e5 + 2;int n,root;int now;int h[Ms],num; struct AC{ int to,next;}t[Ms]; void ADD(int x,int y){ t[++num].to=y; t[num].next=h[x]; h[x]=num;} int ans; void dfs(int u){ for(int j=h[u];j;j=t[j].next) { if(j<now) ++ans; dfs(j); ///continue dfs }}int main(){ freopen("counttree.in","r",stdin); freopen("counttree.out","w",stdout); n=reads(); int QAQ,sss=n,i=1; while(sss--) { ///i‘s dad is dad[i] QAQ=reads(); ADD(QAQ,i); i++; } for(int i=1;i<=n;++i) { now=i; ans=0; dfs(i); printf("%d\n",ans); } return 0;}
cogs2039树的统计 x
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。