F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:本站提供各级各类比赛备战资源(Noip提高组及以下),有意者请联系Lydsy2012@163.com,仅限教师及家长用户。
Problem 5423. -- 数学基友

5423: 数学基友

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 4  Solved: 4
[Submit][Status][Discuss]

Description

作为一个男女比例4:1的班级,fish的班上充满了的好伙 (ji) 伴 (you),一共q对。上帝为之动容,决定送给每一
对好伙伴一些礼物--《数学之(ji)友》。上帝很调皮,把这些数学之友用绳子连了起来(不要问我是怎么连的),
每条绳子链接两本数学之友,细心的fish 发现这些数学之友和绳子构成了一棵无根树!可上帝不好意思让同学们
做太多的作业,决定少给他们一些,于是上帝对每一对好伙伴说:"你们两个从这些数学基友挑出几本来做做就行
了。每人可以挑出形成一条链的数学之友,不过两个人可不能抢同一本哦,所以你们两个挑的链不能包含同一本数
学之友。"这q对基友全部都是丧心病狂的学霸,他们希望获得尽量多的作业,同时因为两个人关系特别好,所以希
望获得的作业总数最多。上帝为每一对好基友提供了一棵树的数学基友让他们来挑,细心的fish 又发现,这些树
都是某一棵有n个节点的无根树的一部分,对于第i对基友,就是这棵树上以xi点为根、yi点所在的子树。现给出这
棵n个节点的树以及xi和yi,fish想知道每一对基友最多能获得多少本数学基友。

Input

给定一棵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

Output

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

Sample Input

7
1 2
1 3
3 4
3 5
4 7
4 6
3
1 1
7 3
3 5

Sample Output

7
4
1
【HIN】
"不相交"指两条路径不共用同一个节点。
一条路径可以为空(包含0个节点)或只包含1个节点。
"以一个节点x为根,另一个节点y所在子树"指,这棵树以x为整棵树的根时,
树上"以y作为根的子树",具体可以参考样例。特别地,当x=y时表示整棵树。
【样例解释】
对于第一个询问,所询问的子树就是原树,两条路径可以为2-1-3-5和6-4-7,总节点数为7

HINT

Source

[Submit][Status][Discuss]

HOME Back