即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

Educational Codeforces Round 22 C. The Tag Game(思维)

编程语言 qq_33183401 22℃ 0评论

C. The Tag Game


time limit per test1 second


memory limit per test256 megabytes


inputstandard input


outputstandard output


Alice got tired of playing the tag game by the usual rules so she offered Bob a little modification to it. Now the game should be played on an undirected rooted tree of n vertices. Vertex 1 is the root of the tree.

Alice starts at vertex 1 and Bob starts at vertex x (x ≠ 1). The moves are made in turns, Bob goes first. In one move one can either stay at the current vertex or travel to the neighbouring one.

The game ends when Alice goes to the same vertex where Bob is standing. Alice wants to minimize the total number of moves and Bob wants to maximize it.

You should write a program which will determine how many moves will the game last.

Input


The first line contains two integer numbers n and x (2 ≤ n ≤ 2·105, 2 ≤ x ≤ n).

Each of the next n - 1 lines contains two integer numbers a and b (1 ≤ a, b ≤ n) — edges of the tree. It is guaranteed that the edges form a valid tree.

Output


Print the total number of moves Alice and Bob will make.

Examples


input


4 3


1 2


2 3


2 4


output


4


input


5 2


1 2


2 3


3 4


2 5


output


6


题解:在一棵n个节点n-1条边的树上,两个人做游戏,A在树根,B在节点x,俩人轮流走,每次走一步或停在原地,B先开始。问A多长时间能抓到B.


题解:因为是B先走,所以他可以到这个点所在链的最大深度,


他可以在不让A抓住的前提下向上找一条深度更大的链。所以预处理出每个点可以到达的最大深度。答案为所能到达的最大深度*2.


代码:

#include
#include
#include
#include
#include
#include
using namespace std;
const int N = 200000 + 100;
int n,x;
struct node
{
    int to,next;
}edge[N<<2];
int head[N<<2];
int f[N];
int mxdp[N];
int dep[N];
int cnt=0;
void add(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void dfs(int u,int pre,int deep)
{
    f[u]=pre;
    mxdp[u]=dep[u]=deep;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==pre)continue;
        dfs(v,u,deep+1);
          mxdp[u]=max(mxdp[u],mxdp[v]);
    }
   // cout<
}
int u,v;
int main()
{
    memset(head,-1,sizeof(head));
    std::ios::sync_with_stdio(false);
    cin>>n>>x;
    for(int i=1;icin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1,1,0);
    int ans=mxdp[x]*2;
    for(int i=0,k=x;iif(i2);
        }
        else
        break;
    }
    cout<

转载请注明:CodingBlog » Educational Codeforces Round 22 C. The Tag Game(思维)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情