There is a kingdom called Dream Kingdom with N cities connected by N - 1 roads. There is a path between any two city. The length of each road is one kilometer. The cities are numbered from 1 to N. There are M X-men in this kingdom. The i-th X-man is in the city numbered ai. There can be no or multiple X-men in one city.Now the king wants you to help him calculate the expected hours he could arrest the X-men. In other words, you need to calculate the expected hours such that all X-men stop moving.
There is a kingdom called Dream Kingdom with N cities connected by N - 1 roads. There is a path between any two city. The length of each road is one kilometer. The cities are numbered from 1 to N. There are M X-men in this kingdom. The i-th X-man is in the city numbered ai(1 ≤ ai ≤ N). There can be no or multiple X-men in one city. Everyone start to walk simultaneously. At the beginning of each hour, one man will choose a adjacent city ("adjacent" means there is a road between two cities) which is on the shortest path to the city where there is a man he can communicate with now. If there are several eligible adjacent cities that can be chosen, the X-man will choose one of themrandomly. Each x-man will make the decision and move simultaneously. The speed of X-men is only one kilometer per hour. So they will move to chosen city at the end of each hour. X-men can communicate with the people whose distance to him ismore than onekilometer at this time. If there are no X-man he can communicate with now, he will not move in the following hour. The king of the Dream Kingdom want to arrest X-men. And at the beginning of one hour he could check whether there is any X-man can move in the following hour. If the king knows no X-man can move in the following hour, he will send the army to catch all X-men immediately. Now the king wants you to help him calculate the expected hours he could arrest the X-men. In other words, you need to calculate the expected hours such that all X-men stop moving.
标签： HBC14303X-Men题解
