小红书 4.9 实习笔试第一题

笔试第一题一看就不会输入输出了，到现在都没用树把这题实现，晚上采用哈希和深度优先搜寻实现了，大佬知道怎么用树实现可以发给我看看

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
unordered_map<int,vector<int>> map;
int dfs(int n)
{
if(map[n].size()==0) return 1;
else
{
if(map[n].size()==1)
{
return 1+dfs(map[n][0]);
}
if(map[n].size()==2)
{
return 1+dfs(map[n][0])+dfs(map[n][1]);
}
}
return 0;
}

int main()
{

int n;
cin>>n;
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
map[b].push_back(a);
}
vector<int> res(n+1,0);
for(int i=1;i<n+1;i++)
{
cout<<dfs(i)<<' ';
int a=dfs(i);
int b=n-dfs(i);
int cha;
if(a-b>0)
{
cha=a-b;
}
else
{
cha=b-a;
}
res[cha]++;
}
cout<<endl;
for(int i=0;i<n;i++)
{
if(res[i]!=0)
{
cout<<i<<' '<<res[i];
}
}
return 0;
}