首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
自动WA
算法工程师
发布于天津
关注
已关注
取消关注
@iworker:
淘天集团笔试0824
题目Q3:小红有一棵传送树,树上有 n 个节点,编号为 1 到 n ,其中 1 号节点为根节点。每个节点都有一个传送门,传送门只可以将小红传送到子树中除了自己的其他节点中编号最小的节点。小红想知道,经过若干次传送门直到叶子节点为止,可以到达的节点数量是多少。输入描述:一行一个整数n,表示树上的节点数量。接下来n - 1行,每行两个整数u, v,表示u号节点和v号节点之间有一条边。1 < n < 10^51 < u, v < n输出描述:输出一行,n个整数,分别对树上n个节点计算答案。解答#include <iostream>#include <vector>#include <algorithm>using namespace std;vector<vector<int>> edge;vector<int> nxt;int n;/** * @brief DFS the tree from root and update the nxt array to record the node it will reach. * @param root: cur node * @param from: parent of root */void findNext(int root, int from) { for (int v : edge[root]) { if (v == from) { continue; } findNext(v, root); if (nxt[root] == -1 || nxt[root] > min(v, nxt[v])) { nxt[root] = min(v, nxt[v]); } } // leaf node if (nxt[root] == -1) { nxt[root] = root; }}int get(int u) { int cnt = 0; while (nxt[u] != u) { cnt++; u = nxt[u]; } return cnt;}int main() { cin >> n; edge.resize(n + 1); nxt.resize(n + 1); for (int i = 1; i <= n; ++i) { int a, b; cin >> a >> b; edge[a].push_back(b); edge[b].push_back(a); } findNext(1, 0); for (int i = 1; i <= n; ++i) { cout << get(i); if (i != n) { cout << ' '; } else { cout << endl; } }}
点赞 4
评论 4
全部评论
推荐
最新
楼层
网易互娱
校招火热招聘中
官网直投
相关推荐
努力学习的小绵羊
05-18 14:26
已编辑
门头沟学院 计算机类
华为实习入池
佬们知道数通大舞台的软开实习啥时候开奖啊?本科的机会大吗?顺便发个面经攒攒运气时间线3月末投递,4月末完成机考(350左右,一二题满分),5月节后完成所有面试,等开奖ing技术面先复盘机考题目(我完全忘了题目,然后面试官给我共享屏幕看了下),稍微说了下第一题的思路项目经历(大部分技术问题+一些管理问题)没八股,给半小时做题(简易内存池2),十分钟秒了结束后5分钟内短信通过主管面自我介绍项目经历(主要沟通管理问题和过程遇到的难题)压力调节目前有其他面试吗工作地点意向实习时长毕业后工作地点意向一天后官网更新状态显示主管面通过,应该是入池了
华为开奖那些事
华为求职进展汇总
点赞
评论
收藏
转发
牛客294836033号
05-17 09:58
门头沟学院 自动化类
项目如何介绍
各位牛客的大佬们,我这学期开始转Java,目前做了个黑马点评,做到用分布式锁解决一人一单这个地方。现在有点好奇就是在面试的时候面试官让我介绍自己的项目的时候应该怎么介绍,感觉做到我目前这个位置为止都没见到有关于点评的内容,就是登录和抢券,好像没有一个完整的业务需求和难点。求大佬们指点一下
点赞
评论
收藏
转发
幸运sir
04-19 22:39
已编辑
绿盟_渗透测试工程师(实习员工)
腾讯云智
😭😭😭
投递腾讯云智研发等公司10个岗位
点赞
评论
收藏
转发
爱吃香菜的仰泳鲈鱼在求佛
04-19 17:59
南京邮电大学 电子信息类
百度这真的假的?
我们辅导员发的,这个时间点,给这么高?百度是非常缺人吗
投递百度等公司10个岗位
点赞
评论
收藏
转发
鲸鱼很迷茫
昨天 00:10
阿里云_云计算算法工程师(准入职员工)
阿里云暑期实习内推
阿里云2025届可转正实习招聘正式开启,因自己原因错过笔试,错过面试,可以滴滴,能捞就我联系hr处理!百分之六十的offer都是第一个月投递的,大家抓紧投递!【公司介绍】阿里云创立于2009年,是全球领先的云计算及人工智能科技公司。【岗位方向】技术类、运营类、设计类、营销类、产品类、销售类、米哈游、内容类、职能类、风险管理类、数据类等【工作地点】杭州、北京、上海、深圳等城市【内推链接】https://careers.aliyun.com/campus/qrcode/home?code=zur3rFlvZDZFVvuDycNhQt1W3iQgiNxFnm7DI4rjOoU%3D(简历优先被筛选,...
投递阿里云等公司10个岗位 >
点赞
评论
收藏
转发
点赞
收藏
评论
分享
回复帖子
提到的真题
返回内容
全站热榜
1
...
开摆了,写小说去了
8358
2
...
没offer的我们也很优秀偶
7035
3
...
【有奖活动】浅聊一下我的实习⭐
6604
4
...
华为暑期开奖
6174
5
...
华为实习offer!终于告一段落了
5735
6
...
双非本 腾讯WXG暑期已offer | 附面经
5416
7
...
滴滴秋储-服务端开发 OC
5145
8
...
快手二面凉经
4455
9
...
快手客户端开发工程师(1)
4288
10
...
帮助大家答疑
4179
正在热议
#
牛客帮帮团来啦!有问必答
#
819721次浏览
13018人参与
#
机械制造薪资爆料
#
319769次浏览
3731人参与
#
晒一晒我的offer
#
3464589次浏览
55247人参与
#
0offer是寒冬太冷还是我太菜
#
427607次浏览
4939人参与
#
你觉得找工作该拿大厂还是小厂练手
#
61544次浏览
870人参与
#
荣耀求职进展汇总
#
70523次浏览
717人参与
#
如果可以选,你最想从事什么工作
#
185886次浏览
3074人参与
#
实习生应该准时下班吗
#
80700次浏览
592人参与
#
金三银四,你有感觉到吗
#
328824次浏览
4215人参与
#
海康威视求职进展汇总
#
101515次浏览
1216人参与
#
正在春招的你,也参与了去年秋招吗?
#
136380次浏览
1705人参与
#
实习必须要去大厂吗?
#
13814次浏览
218人参与
#
实习工作,你找得还顺利吗?
#
42325次浏览
468人参与
#
我在牛爱网找对象
#
49526次浏览
319人参与
#
软件开发投递记录
#
478979次浏览
7241人参与
#
宁德时代求职进展汇总
#
37018次浏览
413人参与
#
国企vs私企,你更想去?
#
20261次浏览
205人参与
#
求职遇到的搞笑事件
#
19655次浏览
287人参与
#
想实习转正,又想准备秋招,我该怎么办
#
117677次浏览
1327人参与
#
正在实习的你,有转正机会吗?
#
106324次浏览
1043人参与
牛客网
牛客企业服务