数学基友

内存限制：512 MiB 时间限制：10 Sec

提交提交记录讨论

作为一个男女比例4:1的班级，fish的班上充满了的好伙 (ji) 伴 (you)，一共q对。上帝为之动容，决定送给每一

对好伙伴一些礼物--《数学之(ji)友》。上帝很调皮，把这些数学之友用绳子连了起来（不要问我是怎么连的），

每条绳子链接两本数学之友，细心的fish 发现这些数学之友和绳子构成了一棵无根树！可上帝不好意思让同学们

做太多的作业，决定少给他们一些，于是上帝对每一对好伙伴说："你们两个从这些数学基友挑出几本来做做就行

了。每人可以挑出形成一条链的数学之友，不过两个人可不能抢同一本哦，所以你们两个挑的链不能包含同一本数

学之友。"这q对基友全部都是丧心病狂的学霸，他们希望获得尽量多的作业，同时因为两个人关系特别好，所以希

望获得的作业总数最多。上帝为每一对好基友提供了一棵树的数学基友让他们来挑，细心的fish 又发现，这些树

都是某一棵有n个节点的无根树的一部分，对于第i对基友，就是这棵树上以xi点为根、yi点所在的子树。现给出这

棵n个节点的树以及xi和yi，fish想知道每一对基友最多能获得多少本数学基友。

给定一棵n个节点的无根树，共q次询问，

每次询问给定两个节点xi和yi（可能xi=yi），

表示对"以xi为根、节点yi所在子树"询问以下答案：

在子树内找两条不相交的路径，使两条路径所包含的节点总数最多。

第1行一个整数n，表示这棵树的节点数，

第2到第n行每行两个整数x,y，表示树上x节点与y节点之间有一条边

第n+1行有一个整数q

接下来q行每行两个整数xi,yi，表示一次询问，xi,yi含义同题目描述

1<=n<=100000,1<=q<=200000,1<=xi,yi<=n

共q行，对于每个询问输出一行一个整数，表示两条路径包含的最多的节点总数

样例输入

样例输出


			7

4

1

【HIN】

"不相交"指两条路径不共用同一个节点。

一条路径可以为空（包含0个节点）或只包含1个节点。

"以一个节点x为根，另一个节点y所在子树"指，这棵树以x为整棵树的根时，

树上"以y作为根的子树"，具体可以参考样例。特别地，当x=y时表示整棵树。

【样例解释】

对于第一个询问，所询问的子树就是原树，两条路径可以为2-1-3-5和6-4-7，总节点数为7

#5423. 数学基友

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示