2526. [Poi2011]Inspection
#2526. [Poi2011]Inspection
题目描述
The railway network of the Byteotian Railways (BR) consists of bidirectional tracks connecting certain pairs of stations. Each pair of stations is connected by at most one segment of tracks. Furthermore, there is a unique route from every station to every other station. (The route may consist of several segments of tracks, but it may not pass through any station more than once.)
Byteasar is an undercover inspector of the BR. His job is to pick one of the stations (denote it by S) for centre of his operations and to travel to all other stations. His journey should be as follows:
-
Byteasar starts in station S. -
Next, he picks one of the stations he did not yet control and goes to it along the shortest path (by train, of course), inspects the station, and then goes back to S. -
The crooked employees of BR warn one another of Byteasar's comings. To deceive them, Byteasar picks the next station for control in such a way that he sets off from the station Sin different direction than the last time, i.e., along a different segment of tracks leaving from S. -
Each station (except S) is inspected exactly once. -
After inspecting the last station Byteasar **does not come back** to S.
The travel time along every segment of tracks takes the same amount of time: one hour.
Byteasar intends to consider all the stations as the initial station S. For each of them he wants to know the order of inspecting the remaining stations that minimises the total travel time, provided that it is possible at all for that particular S.
Byteasar是Byteoian Railways的一名便衣巡视员。BR的铁路架构是一棵N个节点的树，Byteasar需要检查所有的N个节点。他按照如下方式行动：
首先选定一个行动中心S，并且检查S。
从S出发前往任意一个未检查的点（沿树上两点的唯一最短路走），检查该节点，然后返回S。
特别地，检查完最后一个节点后不需要返回。
检查节点不需要时间，走过一条路的时间为1。
为了不暴露身份，Byteasar规定相邻两次检查所经过的道路不允许有重复。
也就是说，除第一次检查之外，他每次从S出发走过的第一条边不能和上一次出发相同。
输入：
第一行是一个整数N。(1<=n<=1000000)
接下来N-1行每行有2个整数A,B，表示A和B之间有一条边。
输出：
N行，第I行表示如果以I作为行动中心，Byteasar检查完所有车站需要的最小时间。如果不可能做到，该行输出-1。
输入格式
The first line of the standard input contains a single integer N(1<=N<=1000000) that denotes the number of stations. These are numbered from 1 to n . The following n -1 lines specify the track segments, one per line. Each of them holds two integers a,b(1<=A,B<=N,A<>B), separated by a single space, indicating that there is a track segment connecting the stations a and b. Each track segments appears exactly once in the description.
In tests worth at least 30% of the points it holds additionally that n<=2000.
输出格式
Your program should print lines on the standard output, each holding a single integer. The one in the i-th line should be the minimum number of hours Byteasar has to spend travelling to inspect the stations when s=i- if inspecting them all is possible for s=i; if it is not, the i-th line should hold the number -1.
样例
样例输入
9
3 6
2 4
2 6
2 5
1 7
2 7
8 9
7 8
样例输出
-1
23
-1
-1
-1
-1
-1
-1
-1