按要求建立BST树
然后层序遍历，统计每层的个数和最大层数，按要求输出最后两行个数就好。
#include <iostream> #include <algorithm> #include <climits> #include <cstring> #include <stack> #include <queue> #include <map> #include <set> #include <string> #define MAX 10010 using namespace std; int n; struct node{ vector <int> next; double m_estate; double area; node() {m_estate = 0 ; area = 0;}; }; node m[MAX]; bool isVis[MAX]; struct Ans{ int c; double avg_sets; double avg_area; int id; }; vector <Ans> ans; Ans NowAns; void LevelOrder(int st){ NowAns.id = st; NowAns.avg_area = m[st].area; NowAns.avg_sets = m[st].m_estate; NowAns.c = 1; isVis[st] = false; queue <int> q; q.push(st); while(!q.empty()){ int top = q.front(); q.pop(); for(int i = 0; i < m[top].next.size();i++){ int v = m[top].next[i]; if(isVis[v]){ isVis[v] = false; q.push(v); if(v <NowAns.id) NowAns.id = v; NowAns.avg_area += m[v].area; NowAns.avg_sets += m[v].m_estate; NowAns.c ++; } } } NowAns.avg_area /= double(NowAns.c); NowAns.avg_sets /= double(NowAns.c); ans.push_back(NowAns); } bool cmp(Ans a1, Ans a2){ if(a1.avg_area != a2.avg_area) return a1.avg_area > a2.avg_area; else return a1.id < a2.id; } int main(){ scanf("%d",&n); memset(isVis,false,sizeof(isVis)); for(int i =0 ; i < n ;i++){ int id,fa,ma,k; scanf("%d%d%d%d",&id,&fa,&ma,&k); isVis[id] = true; if(fa != -1){ m[id].next.push_back(fa); m[fa].next.push_back(id); isVis[fa] = true; } if(ma != -1){ m[id].next.push_back(ma); m[ma].next.push_back(id); isVis[ma] = true; } int cid; for(int j = 0 ; j < k ;j++){ scanf("%d",&cid); isVis[cid] = true; m[id].next.push_back(cid); m[cid].next.push_back(id); } scanf("%lf%lf",&m[id].m_estate,&m[id].area); } for(int i = 0; i < MAX ;i++){ if(isVis[i]){ LevelOrder(i); } } sort(ans.begin(),ans.end(),cmp); printf("%d\n",ans.size()); for(int i = 0 ; i< ans.size() ;i++) printf("d %d %.03lf %.03lf\n",ans[i].id,ans[i].c,ans[i].avg_sets,ans[i].avg_area); return 0; }