当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

5300:Angry Trees

题目描述
JRY is so rich that he bought too many trees and planted them in his yard. Because of his personal preference, all these trees have the same shape. At first, these trees were small and peaceful, but after growing for several years, they become huge and compete for the limited water and nutrition. Therefore, they become angry, and their common enemy is JRY, because it is JRY who planted them in such a "small" place (although his yard is the biggest in the world).

There are $m$ angry trees, and each angry tree has $n$ nodes and $n-1$ branches. All the angry trees decide to combine together, and they made extra $m-1$ branches so that they can be one. Moreover, they select the first node of the first tree to be the root of the whole huge tree. Now, there is a terribly enormous tree with $nm$ nodes and $nm-1$ branches.

The trees come up with an idea to revenge. When JRY is sleeping, they drag JRY onto one of the nodes, and steal all JRY's money and put it onto one node too (the two nodes can be either same or different). When JRY wakes up, he definitely will go for these money. Every time JRY moves down along a branch (moving towards the root), he will spend $1$ unit time, and when he moves up along a branch (moving away from the root), he will spend $2$ unit time. Additionally, smart JRY will always move along the shortest path on the tree between him and his money.

One nightmare of the trees is to find the longest time that JRY need to find his money, and they also need to know how many different ways there are to get this longest time (two ways are considered different if and only if JRY's initial position is different or the money's position is different). Can you help them?
输入解释
The first line of the input is a single integer $T$, indicating the number of testcases.

For each testcase, the first line is two integers $n$ and $m \ (1 \le n, m \le 50000)$. Each of the next $n-1$ lines contains two integers $x$ and $y$, which represent one branch $(x,y)$ in every tree. Each of the following $m-1$ lines contains four integers $x,a,y,b$, which means there is an additional branch connecting the $a$-th node of the $x$-th tree and the $b$-th node of the $y$-th tree. It is guaranteed that either every small tree or the whole tree is an acyclic connected undirected graph. Please be aware that the first node (the node numbered $1$) of the first tree (the tree numbered $1$) is the root of the whole tree.

It is guaranteed that for all the testcases, $\sum n + \sum m \le 1000000$.
输出解释
For each testcase, print two space-separated integers indicating the longest time JRY need to find his money and the ways of position to reach this upper bound.
输入样例
2
3 3
3 1
2 1
3 1 2 2
1 3 2 1
3 8
3 1
2 3
4 3 3 1
3 1 2 3
6 2 1 3
8 3 7 3
5 3 7 3
6 3 7 2
8 3 2 2
输出样例
11 2
22 3

提示
Please be careful about the problem named STACK_OVERFLOW
来自杭电HDUOJ的附加信息
Author XJZX
Recommend wange2014

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-5300

最后修改于 2020-10-25T23:21:28+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
12000/6000MS(Java/Others) 262144/262144K(Java/Others)