2023-04-10 14:54 已编辑 中国科学院大学 C++
关注
小红书 4.9 实习笔试第一题
笔试第一题一看就不会输入输出了，到现在都没用树把这题实现，晚上采用哈希和深度优先搜寻实现了，大佬知道怎么用树实现可以发给我看看
#include
#include
#include
using namespace std;
unordered_map> 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
int a,b;
cin>>a>>b;
map[b].push_back(a);
}
vector res(n+1,0);
for(int i=1;i
cout<
int b=n-dfs(i);
int cha;
if(a-b>0)
{
cha=a-b;
}
else
{
cha=b-a;
}
res[cha]++;
}
cout<
if(res[i]!=0)
{
cout<
}
return 0;
}
#include
#include
#include
using namespace std;
unordered_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
int a,b;
cin>>a>>b;
map[b].push_back(a);
}
vector
for(int i=1;i
cout<
int b=n-dfs(i);
int cha;
if(a-b>0)
{
cha=a-b;
}
else
{
cha=b-a;
}
res[cha]++;
}
cout<
if(res[i]!=0)
{
cout<
}
return 0;
}
全部评论
牛客973607955号 楼主
楼主 中国科学院大学 C++
题目描述：
输入一棵树 T，你需要删除一条边，这棵树会被分成A 和 B 两棵树。你需要让两部分的节点数的差的绝对值| |A|-|B| |尽可能小。输出最小的| |A|-|B| |和最优方案的数量。
输入描述
第一行一个整数 n表示节点的数量，节点从1 到 n编号。
接下来n-1行每行两个正整数 s t，表示s的父亲是t。
输入保证是一棵树。
对于所有数据 1<=n<=100000。
输出描述
输出一行，两个整数，用空格分开，分别表示最优解和最优方案数。
样例输入
3
2 1
3 1
样例输出
1 2
*/
STX5
电子科技大学 golang
谁说这是二叉树了。。。
cs1033
门头沟学院 数据库工程师
从根节点开始递归求出每个子树的节点个数，然后就好做了。
相关推荐
小张frog：去码头整点薯条吃吃吧。大家都会有光明的未来！ 点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
11-27 23:32
华为工作强度 826人发布 点赞 评论 收藏
分享