#abc0194. [abc019_4]高橋くんと木の直径

[abc019_4]高橋くんと木の直径

  1. 现定义树的直径为树上一点到另一点的最大距离。现在有一棵树,每条边的长度不超过1e6,给出他的节点数n(2≦N≦50)。你可以询问任意两点的距离(最大)。
  2. 询问格式为
  3. ? a b
  4. 表示询问节点a到节点b的距离,随后得到一个数,表示节点a到节点b的距离(最大)。
  5. 请你在询问次数限制内求出树的直径。
  6. 20%的点可以询问1300次,80%的点可以询问100次。注意每次询问后关掉输出文件,否则可能会TLE,以c语言为例
printf("? %d %d\n",&a, &b);
fflush(stdout);
scanf("%d", &dist);
  1. 如图给出一组样例
  2. 输入
5
5
1
2
9
8
  1. 输出
? 1 2
? 2 4
? 4 5
? 2 3
? 1 5
! 14//树的直径