813C The Tag Game --- DFS

待我称王封你为后i 2021-12-07 14:11 135阅读 0赞

追逐游戏啊，[?][Link 1] //沧桑脸

下回把dfs，bfs，dijkstra都写一遍~

//[DFS和BFS区别][DFS_BFS]

（1）dfs学了这篇：[https://blog.csdn.net/mengxiang000000/article/details/72901402][https_blog.csdn.net_mengxiang000000_article_details_72901402]

但是。。。我没有理解遇到两人到某点距离一样，就更新答案这句，而且，不加这句也ac了，搞不明白<(＿　＿)>

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 #define mem(a) memset(a,0,sizeof(a))
     3 #define ll long long
     4 #define inf 0x3f3f3f3f
     5 const int N=2e5+5;
     6 const int M=1e3+10;
     7 const ll lim=1e14+5;
     8 using namespace std;
     9 int ans,dis[2][N];
    10 vector<int>ve[N];
    11 void dfs(int now,int from,int judge,int sum)
    12 {
    13    dis[judge][now]=sum;
    14    if(judge==1&&sum<dis[0][now])
    15    {
    16        ans=max(ans,dis[0][now]*2);//停
    17    }
    18    for(int i=0;i<ve[now].size();i++)
    19    {
    20         int now1=ve[now][i];
    21         if(now1==from) continue;
    22         dfs(now1,now,judge,sum+1);
    23    }
    24 }
    25 int main()
    26 {
    27     int n,x,a,b;
    28     scanf("%d%d",&n,&x);
    29     for(int i=0;i<n-1;i++)
    30     {
    31         scanf("%d%d",&a,&b);
    32         ve[a].push_back(b);
    33         ve[b].push_back(a);
    34     }
    35     dfs(1,0,0,0);
    36     dfs(x,0,1,0);
    37     printf("%d\n",ans);
    38     return 0;
    39 }

转载于:https://www.cnblogs.com/XXrll/p/11169609.html

[Link 1]: http://codeforces.com/contest/813/problem/C
[DFS_BFS]: https://blog.csdn.net/github_38818603/article/details/81288659
[https_blog.csdn.net_mengxiang000000_article_details_72901402]: https://blog.csdn.net/mengxiang000000/article/details/72901402
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211207/7c8f3183656c43588724303492487615.png