DFS/最大路径长度-CodeForces 813C-The Tag Game

骑猪看日落 2022-05-16 12:12 149阅读 0赞

*  # DFS/最大路径长度-CodeForces 813C-The Tag Game #

--------------------

*  ## 题目链接：[C. The Tag Game][] ##
 *  ## 思路： ##

给定一颗以1为根的无向树，Alice在1节点，Bob在x节点，两人交替操作，每一次操作可以选择移动到相邻的一个节点或者不动，Bob希望两人越晚相遇越好，Alice希望越早越好，Bob先操作，问两人最后会在一共经历多少次操作后相遇？

![Center][]

**B**: go to vertex 3

**A**: go to vertex 2

**B**: go to vertex 4

**A**: go to vertex 3

**B**: stay at vertex 4

**A**: go to vertex 4

**首先Alice肯定是背离1结点方向去追Bob，所以对于Bob来说，要让相遇越晚只有两种可能：**

1.往叶子方向走，找到最深叶子方向并进入

2.先**往上**走找分岔口，有可能寻找到**一个分支到叶子的路径更长的方向**，在此情况下**必须满足在走到这个分岔口的时候与Alice没有相遇！**

**因为Alice始终会到达叶子，所以操作数：1到Bob逃往的叶子结点深度\*2**

*  ## 总结： ##

自己很少遇到深搜和图的题目，借鉴dalao文章总结下收获

**1.求经过某个结点的路径的最大深度：**递归搜索到叶子后的返回是一个回溯到上一结点的过程，通过返回后比较当前结点与下一结点的深度值（去最大），可以记录下经过当前结点的路径的最大深度

**2.树的构建：**用向量数组建树，双向构建以保存父结点值，判断是否为叶子只需满足：当前结点Now指向的结点不为标记的上一结点Pre

**3.对经过某个结点的路径的最大深度的误解：**一开始不理解第二种情况，向上寻找分叉进入一个更深的叶子，Max\_Depth\[i\]并不是整棵树的最长路径，只是通过该结点i的若干路径的最大深度！！！所以向上走是有可能找到一个分支，使得到叶子的路径更长！也就是Max\_Depth\[i\]越大

*  ## 代码： ##

#include<iostream>
    #include<algorithm>
    #include<vector>
    using namespace std;
    #define MAX_SIZE 200005
    
    vector<int> Tree[MAX_SIZE];
    int Max_Depth[MAX_SIZE];    
    int Depth[MAX_SIZE];    //当前结点的深度
    int Pre[MAX_SIZE];  //记录遍历结点的上一个位置
    
    void DFS(int now,int pre,int dep)
    {
        Depth[now]=Max_Depth[now]=dep;     
        Pre[now]=pre;
        for(int i=0;i<Tree[now].size();i++)
        {
            int Next=Tree[now][i];
            if(Next!=pre)    //当该结点不是叶子
            {
                DFS(Next,now,dep+1);
                Max_Depth[now]=max(Max_Depth[now],Max_Depth[Next]);  //通过递归回溯的特点记录从根通过该叶子的最大路径长度
            }
        }
    }
    
    int main()
    {
        int n,x,a,b;
        cin>>n>>x;
        for(int i=0;i<n-1;i++)  //建树
        {
            cin>>a>>b;
            Tree[a].push_back(b);
            Tree[b].push_back(a);
        }
        DFS(1,0,0);
        int Max_Path=Max_Depth[x]*2;
        int Pre_ip=x;
        for(int i=0;i<Depth[x];i++)  //寻找可能存在的x前面的分岔口，让x的进入深度更深
        {
            if(i<Depth[Pre_ip])   //在两个人不能在分岔口相遇的情况下
                Max_Path=max(2*Max_Depth[Pre_ip],Max_Path);
            else
                break;
            Pre_ip=Pre[Pre_ip];    //再回到上一结点
        }
        cout<<Max_Path<<endl;
        return 0;
    }

*  ## 参考文章： ##

### [Dust\_Heart- Educational Codeforces Round 22 C The Tag Game（树的深度）][Dust_Heart- Educational Codeforces Round 22 C The Tag Game] ###

**很棒的一个博主，主打ACM**

[C. The Tag Game]: http://codeforces.com/problemset/problem/813/C
[Center]: /images/20220516/e68e8eed6cc04c52b843fc0e43db311b.png
[Dust_Heart- Educational Codeforces Round 22 C The Tag Game]: https://blog.csdn.net/my_sunshine26/article/details/74781101