201503-4 ccf 网络延时(dfs)

刺骨的言语ヽ痛彻心扉 2022-05-13 23:39 166阅读 0赞

题目链接：  
[网络延时][Link 1]

题目大意：  
中文题目，不解释2333

解题思路：  
在树上找最远的两点距离，我们可以知道，其中一个点必定是离根结点最远的一点，即深度最大的（证明略，应该很容易理解吧2333），那么我们只需要从深度最大的某个点出发，dfs一遍，最远的那个距离就是答案。

AC代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <vector>
    
    using namespace std;
    
    vector<int> g[20010];
    
    int depth[20010],vis[20010];
    int ans,start,maxdep;
    
    void dfs(int u,int step){
        ans = max(ans,step);
        vis[u] = 1;
        for(int i=0; i<g[u].size(); ++i){
            int v = g[u][i];
            if(!vis[v]){
                dfs(v, step+1);
            }
        }
        return ;
    }
    
    void init(){
        memset(depth, 0,sizeof(depth));
        memset(vis, 0, sizeof(vis));
        ans = maxdep = 0;
        depth[1] = 0;
    }
    
    int main(){
    
        int n,m;
        cin>>n>>m;
        int cnt = 1;
        for(int i=0; i<n-1; ++i){
            int f;
            scanf("%d",&f);
            g[f].push_back(++cnt);
            g[cnt].push_back(f);
            depth[cnt] = depth[f] + 1;
            if(depth[cnt] > maxdep){
                maxdep = depth[cnt];
                start = cnt;
            }
        }
        for(int i =0; i<m; ++i){
            int f;
            scanf("%d",&f);
            g[f].push_back(++cnt);
            g[cnt].push_back(f);
            depth[cnt] = depth[f] + 1;
            if(depth[cnt] > maxdep){
                maxdep = depth[cnt];
                start = cnt;
            }
        }
    
        dfs(start,0);
        cout<<ans<<endl;
        return 0;
    }

[Link 1]: http://118.190.20.162/view.page?gpid=T24