問題文
高桥君痴迷于寻找树的直径。 树是由顶点和连接它们的边组成的结构“图”。 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 |
这是输入/输出的示例,并不一定意味着您正在问一个有意义的问题。