2023-09-28 20:51 已编辑 门头沟学院 C++
关注
滴滴笔试记录一下思路，没过完全
不知道哪里出了问题，各位大佬看看
1. 记忆化搜索，我是拿一个 (a[0]<<24)|(a[1]<<16)|(a[2]<<8)|i来记忆化，首先要排序a，然后搜i，然后记忆化
2. 换根dp，第一遍dfs，求根节点到所有节点的距离，并求出每一个节点的子节点有多少个，记录在Node数组里；第二遍dfs，记当前节点cur到其他节点的距离为S，则有S[cur]=S[fa]+N-Node[cur]，其中N代表节点个数。
1. 记忆化搜索，我是拿一个 (a[0]<<24)|(a[1]<<16)|(a[2]<<8)|i来记忆化，首先要排序a，然后搜i，然后记忆化
2. 换根dp，第一遍dfs，求根节点到所有节点的距离，并求出每一个节点的子节点有多少个，记录在Node数组里；第二遍dfs，记当前节点cur到其他节点的距离为S，则有S[cur]=S[fa]+N-Node[cur]，其中N代表节点个数。
全部评论
相关推荐
不愿透露姓名的神秘牛友
昨天 23:19
投递大疆等公司10个岗位 > 点赞 评论 收藏
分享
