← 返回题目列表

AtCoder · abc019_4

D. 高桥君和树的直径

中文机器翻译题面 查看原题

問題文

高桥君痴迷于寻找树的直径。 树是由顶点和连接它们的边组成的结构“图”。 1 通过种子指定顶点数。 N ,则边为 N-1 有一本书,每个顶点都通过边间接或直接连接到其他每个顶点。

在这个问题中,边具有整数权重。两个顶点之间的距离定义为连接两个顶点的边的权重之和。

树的直径是两个最远顶点之间的距离。

考虑以下树。写在边上的数字就是该边的权重。

在这种情况下,顶点 1 和 我讨厌 2 的距离是 1、頂点 2 和 我讨厌 4 之间的距离是 1+2=3 。顶点 3 和 我讨厌 5 之间的距离是 3+4=7、頂点 4 和 我讨厌 5 之间的距离也是 2+1+4=7 并且这个距离是这棵树的顶点之间的最大距离,所以树的直径是 7 。

Takahashi-kun 计算顶点数并 2 我对根据顶点之间的距离信息查找树的直径感兴趣。 在这个问题中,你有树中的顶点数 最初给出 N ,2 通过询问几个有关顶点之间距离的问题来查找树的直径。

但是,2 询问顶点之间距离的次数是有限制的。

编写一个程序,在有限数量的问题内查找树的直径。


入出力

一、树的顶点数 N 被赋予标准输入。

N

然后,您的程序会多次询问响应程序。问题的格式如下。

? a b

在这个问题中,a,b 之间的距离在一行中传递到标准输入。 必须满足1 ≦ a, b ≦ N 和 a≠b 。

问了几个问题后,你猜出了树的直径。树的直径 diameter 以

! diameter

格式输出。打印树木直径后,您的程序必须立即退出。如果测试没有完成,判断结果是不确定的。

另外,以这些以外的格式输出时的判断结果也未定义。

本题中,为每个测试用例设置了提问数量的上限值,如果程序提问的数量超过了上限值,则判定答案不正确。

答案是否正确由输出的树直径决定。即使您只被问到没有指定树直径的问题,如果直径正确,您也会得到正确的答案。


頂点 1 和顶点 询问 2 之间的距离 显示了多种语言的在名为dist 的变量中接收结果的示例。

然而,可以使用这里描述的方法以外的方法来执行输入/输出。

请注意,打印后必须刷新输出。如果不冲洗,可能会发生 TLE。

C

printf("? %d %d\n", 1, 2);
fflush(stdout);
scanf("%d", &dist);

C++

cout << "? " << 1 << " " << 2 << endl;
cin >> dist;

Java

System.out.printf("? %d %d\n", 1, 2);
Scanner scanner = new Scanner(System.in);
dist = scanner.nextInt();

C#

Console.WriteLine("? {0} {1}", 1, 2);
dist = int.Parse(Console.ReadLine());

D

writeln("? ", 1, " ", 2);
stdout.flush();
dist = readln.chomp.to!int;

PHP

echo "? ", 1, " ", 2, PHP_EOL;
$dist = trim(fgets(STDIN));

Python

print "? {0} {1}".format(1, 2)
sys.stdout.flush()
dist = int(raw_input())

Perl

$|=1;
print "? ", 1, " ", 2, "\n";
$dist = <>;

红宝石

print "? ", 1, " ", 2, "\n"
STDOUT.flush
dist = gets.to_i

制約

  • 2 ≦ N ≦ 50
  • 1 ≦ (それぞれの辺の重み) ≦ 10^6

部分点

针对此问题设置了部分分数。

  • 20 在一个值得积分的测试用例中,问题数量上限为1300。
  • 另一个 80 在有价值的测试用例中,问题数量的上限为100。

入出力例

当树具有以下形状时,

可以进行以下输入/输出。

程序的输入 程序输出
5
? 1 2
5
? 2 4
1
? 4 5
2
? 2 3
9
? 1 5
8
! 14

这是输入/输出的示例,并不一定意味着您正在问一个有意义的问题。