As a member of Coffee Chicken, ZYB is a boy with excellent data structure skills. Consider the following problem: Give a rooted tree withN{N}Nvertices. Vertices are numbered from 1{1}1to N{N}N, and the root is always vertex 1{1}1. You are allowed to assign at mostK{K}Kkey verticesso that the maximum ancient distances amongall vertices isas small as possible. Denote theancient distance of vertex x{x}xas: The distance betweenx{x}xand the firstkey vertexon the path fromx{x}xto the root. For example, if the tree is 1-2-3 and the set of key verticesis{2}{{2}}{2}, then the ancient distances of all vertices are{+∞,0,1}{+infty,0,1}{+∞,0,1}. ZYB thenstrengthens this problem: Please find the answerfor eachK∈{1,2,…
As a member of Coffee Chicken, ZYB is a boy with excellent data structure skills. Consider the following problem: Give a rooted tree with N{N}N vertices. Vertices are numbered from 1{1}1 to N{N}N, and the root is always vertex 1{1}1. You are allowed to assign at most K{K}K key vertices so that the maximum ancient distances among all vertices is as small as possible. Denote the ancient distance of vertex x{x}x as: The distance between x{x}x and the first key vertex on the path from x{x}x to the root. For example, if the tree is 1-2-3 and the set of key vertices is {2}{{2}}{2}, then the ancient distances of all vertices are {+∞,0,1}{+infty,0,1}{+∞,0,1}. ZYB then strengthens this problem: Please find the answer for each K∈{1,2,…,N}K in {1,2,dots,N}K∈{1,2,…,N}. Could you accept ZYB's challenge?
