A628.codeforces-1919h
普及-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
H. Tree Diameter
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
There is a hidden tree with 𝑛
vertices. The 𝑛−1
edges of the tree are numbered from 1
to 𝑛−1
. You can ask the following queries of two types:
Give the grader an array 𝑎
with 𝑛−1
positive integers. For each edge from 1
to 𝑛−1
, the weight of edge 𝑖
is set to 𝑎𝑖
. Then, the grader will return the length of the diameter†
.
Give the grader two indices 1≤𝑎,𝑏≤𝑛−1
. The grader will return the number of edges between edges 𝑎
and 𝑏
. In other words, if edge 𝑎
connects 𝑢𝑎
and 𝑣𝑎
while edge 𝑏
connects 𝑢𝑏
and 𝑣𝑏
, the grader will return min(dist(𝑢𝑎,𝑢𝑏),dist(𝑣𝑎,𝑢𝑏),dist(𝑢𝑎,𝑣𝑏),dist(𝑣𝑎,𝑣𝑏))
, where dist(𝑢,𝑣)
represents the number of edges on the path between vertices 𝑢
and 𝑣
.
Find any tree isomorphic‡
to the hidden tree after at most 𝑛
queries of type 1 and 𝑛
queries of type 2 in any order.
†
The distance between two vertices is the sum of the weights on the unique simple path that connects them. The diameter is the largest of all those distances.
‡
Two trees, consisting of 𝑛
vertices each, are called isomorphic if there exists a permutation 𝑝
containing integers from 1
to 𝑛
such that edge (𝑢
, 𝑣
) is present in the first tree if and only if the edge (𝑝𝑢
, 𝑝𝑣
) is present in the second tree.
输入格式
The first and only line of input contains a single integer 𝑛
(3≤𝑛≤1000
) — the number of vertices in the tree.
输入输出样例
输入#1
5 3 1 9 0
输出#1
? 1 1 1 1 1 ? 2 1 3 ? 1 4 3 2 1 ? 2 4 2 ! 3 1 4 2 1 2 2 5
说明/提示
The hidden tree in the example is shown above. The number on the vertices represents the vertex number while the number on the edges represents the edge number.