23.8.13米哈游秋招笔试题记录

第一题

签到题easy

第二题

// 给出一颗有根树，树上有n个节点和n-1条边，边的距离为1. 根节点编号为1.
// 根据上述构建出这棵有根树。
// 然后，进行任意次操作：
// 操作内容：对于树的叶子节点添加一个叶子节点，新添加边长度也是1.
// 问经过操作以后，使得这棵树中所有节点与根节点的距离不超过k的最大值是多少？
// 输入n,k，以及各个边输出满足条件的节点个数
//4 2
//1 2
//1 3
//2 4
//输出
//5

import sys
sys.setrecursionlimit(1000000000)

n,k = list(map(int, input().split()))
G = [[] for i in range(n)]
for i in range(n-1):
	u,v = list(map(int, input().split()))
	G[u-1].append(v-1)
	G[v-1].append(u-1)
def dfs(cur,depth,parent):
	if depth > k:
		return 0
	ans = 1
	if len(G[cur]) > 1 or parent == -1:
		for nei in G[cur]:
			if nei != parent:
				ans += dfs(nei,depth+1,cur)
	else:
		ans += max(0,k-depth)
	return ans
print(dfs(0,0,-1))

其实就是求树满足要求的叶子节点个数每个叶子节点根据深度可以添加k-depth个节点。上面给出的是牛客看到的一位大佬比较简洁的代码@TaylorSwift13

第三题