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

"尚學(xué)堂杯"哈爾濱理工大學(xué)第五屆程序設(shè)計(jì)團(tuán)隊(duì)賽（正式）

題目大意：

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

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

問最慢貓抓到耗子的時(shí)間。

思路：

1、肯定耗子想要跑的盡可能的遠(yuǎn)，而且在跑到那個(gè)終點(diǎn)位子End之前的路徑上，貓不會(huì)抓到耗子。

那么我們可以通過枚舉End這個(gè)點(diǎn)來判斷，對(duì)于一個(gè)點(diǎn)u，如果耗子到達(dá)這個(gè)點(diǎn)的耗用時(shí)間量小于貓到達(dá)這個(gè)點(diǎn)的耗用時(shí)間量，那么這個(gè)點(diǎn)就可以作為End點(diǎn)。而且在這個(gè)點(diǎn)u貓抓到耗子的時(shí)間就是貓到達(dá)這個(gè)點(diǎn)的時(shí)間。

過程維護(hù)最大，那么滿足條件的最大時(shí)間，就是最終答案。

2、因?yàn)轭}目要求耗子和貓都會(huì)做出最優(yōu)的決策，那么肯定是要處理兩次樹上的最短路，處理出來貓和耗子到各個(gè)點(diǎn)的最短路徑長度，然后計(jì)算時(shí)間維護(hù)滿足條件的最大時(shí)間即可。

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);    }}