【CCF CSP-20150304】网络延时

解法一：动态规划

#include
using namespace std;
vectortree[20005];//存储整棵树
int n,m,a;
int dp1[20005],dp2[20005];
void DP(int v){//深度优先遍历
    int max1=0,max2=0;
    for(int i:tree[v]){
        DP(i);
        if(dp1[i]+1>max1){//计算到根结点v到叶子结点的最远距离
            max2=max1;
            max1=dp1[i]+1;
        }else if(dp1[i]+1>max2)//计算到根结点v到叶子结点的第二远距离
            max2=dp1[i]+1;
    }
    dp1[v]=max1;
    dp2[v]=max1+max2;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n+m;++i){
        scanf("%d",&a);
        tree[a].push_back(i);
    }
    DP(1);
    printf("%d",*max_element(dp2+1,dp2+n+m+1));//dp2中最大值即为所求
    return 0;
}

解法二：DFS

#include
using namespace std;
vectortree[20005];//存储整棵树
int n,m,a,ansV=-1,ansLevel=0;//ansV表示距离最远的结点编号，ansLevel表示最远距离
bool visit[20005];//标记每个节点是否已被访问
void DFS(int v,int level){//深度优先遍历
    visit[v]=true;
    if(level>ansLevel){
        ansLevel=level;
        ansV=v;
    }
    for(int i:tree[v])
        if(!visit[i])
        DFS(i,level+1);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n+m;++i){
        scanf("%d",&a);
        tree[a].push_back(i);
        tree[i].push_back(a);//将树的边存储为无向边
    }
    DFS(1,0);//第一次深度优先遍历
    memset(visit,0,sizeof(visit));
    DFS(ansV,0);//二次遍历
    printf("%d",ansLevel);
    return 0;
}