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 ",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 ",ans); } return 0; }