Tom and Jerry

Time Limit: 3000 MS Memory Limit: 327680 K Total Submit: 68(18 users) Total Accepted: 20(16 users) Rating:  Special Judge: No

Description

Tom and Jerry are trapped in a tree with n vertex (2 <= n <= 100000). Initially they are on two different vertex, as we know, jerry will run to his home and tom want to catch jerry before he reach his home. But unluckily, there are no home in this tree, so jerry’s being caught is just a matter of time. Your task is to calculate the minimal time tom can catch jerry (Tom catch Jerry means they are at the some vertex at the same time). To make things simple, we define that every second, Jerry make his choice first and then Tom make his choice. Of course, both of them will choose their way optimally.  We define every move as follow: At every move, Tom or Jerry can choose whether to move to an adjacent vertex or just stay where he is.  We define the speed as follows: Speed v means Tom or Jerry can make at most v moves in every second. You should know that Jerry's speed is always 1, Tom's speed is v.

Input

The first line contains an integer T, then T cases follows.  In each case, there are n+1 lines of input. The first line is a single integer n, indicating the number of vertex numbered from 0 to n-1. Each of the next n-1 lines contains 2 integers a and b, means there is an edge between a and b. The last line contains 3 integers t, j and v(v < min(n, 20)), means the initial place of Tom and Jerry and Tom's speed.

Output

For each case, you should output the minimal time Tom needed to catch Jerry.

Sample Input

290 11 22 33 44 52 66 77 85 0 190 11 22 33 44 52 66 77 80 5 1

Sample Output

65

Source

"尚學堂杯"哈爾濱理工大學第五屆程序設計團隊賽（正式）

題目大意：

現(xiàn)在有N個點的一棵樹，初始的時候貓和老鼠的位子已知，老鼠的速度永遠都是1，貓的速度是V.

對于速度，表示一秒可以進行的操作次數(shù)，每一秒都可以進行兩種操作：移動到相鄰的點，或者是不動。

問最慢貓抓到耗子的時間。

思路：

1、肯定耗子想要跑的盡可能的遠，而且在跑到那個終點位子End之前的路徑上，貓不會抓到耗子。

那么我們可以通過枚舉End這個點來判斷，對于一個點u，如果耗子到達這個點的耗用時間量小于貓到達這個點的耗用時間量，那么這個點就可以作為End點。而且在這個點u貓抓到耗子的時間就是貓到達這個點的時間。

過程維護最大，那么滿足條件的最大時間，就是最終答案。

2、因為題目要求耗子和貓都會做出最優(yōu)的決策，那么肯定是要處理兩次樹上的最短路，處理出來貓和耗子到各個點的最短路徑長度，然后計算時間維護滿足條件的最大時間即可。

Ac代碼：

#include<stdio.h>#include<string.h>#include<vector>using namespace std;vector<int >mp[100600];int vis[100600];int dis[2][100600];void Dfs(int u,int d){    vis[u]=1;    for(int i=0;i<mp[u].size();i++)    {        int v=mp[u][i];        if(vis[v]==0)        {            vis[v]=1;            dis[d][v]=dis[d][u]+1;            Dfs(v,d);        }    }}int main(){    int t;    scanf("%d",&t);    while(t--)    {        int n;        scanf("%d",&n);        memset(dis,0,sizeof(dis));        for(int i=1;i<=n;i++)mp[i].clear();        for(int i=0;i<n-1;i++)        {            int x,y;            scanf("%d%d",&x,&y);            mp[x].push_back(y);            mp[y].push_back(x);        }        int t,j,v;        scanf("%d%d%d",&t,&j,&v);        memset(vis,0,sizeof(vis));        Dfs(t,0);        memset(vis,0,sizeof(vis));        Dfs(j,1);        int ans=0;        for(int i=1;i<=n;i++)        {            int tmp=dis[0][i]/v;            if(dis[0][i]%v!=0)tmp++;            if(tmp>dis[1][i])            {                ans=max(ans,tmp);            }        }        PRintf("%d/n",ans);    }}