寻路 (find.cpp\c\pas)
【问题描述】
至于丁国国王的下场……
大魔王一气之下把他扔进了迷雾森林。迷雾森林可以看作一棵有n个节点的树,根节点为1,但由于”Birds are everywhere.”,他得到了种种不一样的消息,每份消息中都会告诉他有两棵子树是禁忌之地,于是他向你求助了。
他给出了q个形如”x y”的询问,表示他不能走到x和y的子树中,由于走的路径越长他找到出口的概率越大并且他只能走一条不经过重复节点的路径,现在他想知道对于每组询问他能走的最长路径是多少,如果没有,输出零。
你刚刚在对决中打败了大魔王,心情愉悦,决定帮丁国国王一把。
当然,出于本国利益,你也可以不帮他。
【输入格式】
第一行两个正整数n和q(1 ≤ n , q ≤ 100000)
第二到第n行每行两个整数u,v表示u和v之间有一条边连接,边的长度为1。
接下来q行每行两个x,y表示一组询问,意义如题目描述。
【输出格式】
q行,输出见题目描述
【输入输出样例】
find.in
5 2
1 3
3 2
3 4
2 5
2 4
5 4
find.out
1
2
【样例解释】
询问1中2和4的子树不能走,最长路径为(1,3)长度为1
询问2中5和4的子树不能走,最长路径为(1,3,2)长度为2
【数据范围】
对于前20%的数据1 ≤ n,q ≤ 100
对于前50%的数据1 ≤ n,q ≤ 2000
对于100%的数据1 ≤ n ≤ 100000,1 ≤ q ≤ 50000
信息
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 8
- 已通过
- 1
- 通过率
- 12%
- 被复制
- 1
- 上传者