#2149. Hard route

    ID: 2149 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1271来源:qoj.ac数据:公开样例树上算法倍增

Hard route

Hard route

题目描述

XIII Zhautykov Olympiad on Mathematics, Physics and Informatics, Day 2 Almaty, Kazakhstan, January, 15, 2017 Problem F. Hard route Input file: road.in Output file: road.out Time limit: 1 second Memory limit: 256 megabytes — is governor of the country ACMstan. There are N cities and N −1 two-way roads in this Mansur country. It is known that from any city you can go to any other city moving along existing roads. More formally, the country looks like a tree, where the vertices are cities and the edges are two-way roads. Also, in this country, the cities with exactly one connected road called terminal. A route is a simple path from one terminal to another terminal. The distance between two cities is the minimum number of roads on the way between them. The distance from city to the route is the minimum number of roads on the way from given city to any city on the route. Mansur decided to implement exactly one route in ACMstan, however he interested in only hard routes. Hardness of route computed as follows: let A and B are terminals of the route, and H is the maximum distance from any city in the country to this route, then the hardness of route is product of H and the distance between A and B. Mansur asked Temirulan to find maximal hardness over all routes, in fact he is interested to know the number of such routes. Temirulan asking help from you. It’s strongly recommend to read explanation below. Input First line of input contains a positive integer N (2 ≤N ≤500000) — the number of cities in the country. The cities are numbered from 1 to N. The following N −1 lines contain 2 positive integers, separated by single space, ui, vi (1 ≤ui, vi ≤N; ui̸ = vi) — road connecting cities ui and vi. It is guaranteed that the given graph is a tree. Output Output in single line two integers — the maximal hardness and the number of routes, separated by single spaces. Note that, route from A to B and route from B to A are the same routes. Scoring This problem consists of three subtasks:

  1. 2 ≤N ≤100. Score 19 points.
  2. 2 ≤N ≤5000. Score 33 points.
  3. 2 ≤N ≤500000. Score 48 points. Each subtask will be scored if only if the solution successfully passes all of the previous subtasks. Page 3 of 4 XIII Zhautykov Olympiad on Mathematics, Physics and Informatics, Day 2 Almaty, Kazakhstan, January, 15, 2017 Examples road.in road.out 7 6 2 1 2 1 3 2 4 2 5 3 6 3 7 4 2 3 1 2 2 3 2 4 5 0 1 1 2 2 3 3 4 4 5 Note A simple path is a path with no repeated vertices. Note, that there may be simple path which is not route. First sample test: There is four terminal cities with number 4, 5, 6 and 7. For route 4-2-1-3-6, the distance is 4 and distances from other cities to this route is [1, 1], maximum among them is 1, so the hardness of route is equal to 4 × 1 = 4. For route 4-2-5, the distance is 2, maximum distance among other cities is 3 (from 6 or 7), hardness of route equal to 3 × 2 = 6. Hardness of 6-3-7 also 6, but other routes has smaller hardness. In third sample test there is only two terminal cities 1 and 5, so there is exactly one route 1-2-3-4-5, the distance is 4 and maximum distance among all cities to route is 0, because all cities are on this route already. Hardness is equal to 4 × 0 = 0. Page 4 of 4

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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