CodeForces - 813C The Tag Game (树的dfs遍历)

【传送门】http://codeforces.com/problemset/problem/813/C

【题目大意】两个人玩游戏，一个人跑一个人追，轮流决策，可以走也可以不走。给你一棵树，想要从某个结点到达另一个结点当且仅当两个结点有边相连，A从根节点1号点出发，B从X号点出发，B要尽可能躲A，A要尽可能抓住A，最后两个人共决策了多少次。

【题解】可以知道这样一个事实，B一定会躲到离他最远的那个结点，然后A不管怎样决策B都躲在那里不动了。但是有一点需要注意，B需要比A先到达那个叶子结点。

所以问题转化成了分别求A，B到各个叶子结点的距离。选取一个A到达某一叶子结点的最远值，注意还必须满足这个最远值要大于B到达这个叶子结点的距离。

使用DFS对树进行搜索，直到叶子结点，每每遇见一个叶子结点就记下距离。起点分别设置为1和X，距离保存在两个数组中。

【AC代码】

#include<iostream>

#include<cstdio>

#include<string>

#include<algorithm>

#include<vector>

#include<cstring>

#include<iomanip>

using namespace std;

typedef long long ll;

const int maxn = 2e5+;

vector<int> G[maxn];

ll d1[maxn];

ll d2[maxn];

void dfs(int st, int fr, ll step, ll d[]){

    if(G[st].size() ==  && st != ){

        d[st] = step;

        //return ;//这里return会错误

    }

    for(int i=; i<G[st].size(); i++){

        if(G[st][i] != fr){

            dfs(G[st][i] , st, step+, d);

        }

    }

}

int main(){

    int n,x;

    int s,t;

    while(scanf("%d%d",&n,&x) != EOF){

        ll ans = ;

        for(int i=; i<maxn; i++)    G[i].clear();

        memset(d1 ,  ,sizeof d1);

        memset(d2 ,  ,sizeof d2);

        while(scanf("%d%d",&s,&t) != EOF){

            G[s].push_back(t);

            G[t].push_back(s);

        }

        dfs(, -, , d1);

        dfs(x, -, , d2);

        for(int i=; i<=n; i++){

            if(d1[i] > d2[i] && G[i].size() == ){

                ans = max(ans , *d1[i]);

            }

        }

        printf("%lld\n",ans);

    }

    return ;

}

巴特西

CodeForces - 813C The Tag Game (树的dfs遍历)

最新文章

热门文章