題目描述
思路分析
本題所求的實(shí)際上是樹的直徑，即樹中的任意兩個(gè)結(jié)點(diǎn)之間的最大距離
采用的方法是dfs
從根節(jié)點(diǎn)開始遍歷，對(duì)于每一個(gè)被dfs的結(jié)點(diǎn)m，返回此結(jié)點(diǎn)m到所有葉子結(jié)點(diǎn)的距離最大的那個(gè)即d1，同時(shí)在dfs過程當(dāng)中記錄結(jié)點(diǎn)m到所有葉子結(jié)點(diǎn)的距離第二大的那個(gè)，即d2
那么最終答案就是對(duì)于每一個(gè)結(jié)點(diǎn)取res=res(res,d1+d2)
舉個(gè)栗子：
設(shè)最下面的1--4的編號(hào)分別為5,6,7,8
從1開始dfs，首先進(jìn)入2，然后對(duì)2dfs，進(jìn)入3,然后對(duì)3進(jìn)行dfs，對(duì)3dfs的時(shí)候，又進(jìn)入5，對(duì)5dfs，此時(shí)由于結(jié)點(diǎn)5沒有分支，所以這一次dfs得到d1=d2=0，返回給結(jié)點(diǎn)3的值為d1+1=1,之后3也算dfs完畢，結(jié)果：d1=1，d2=0，返回給2的值為d1+1=2，然后開始對(duì)4dfs，此時(shí)會(huì)進(jìn)入下一層，依次對(duì)6,7,8進(jìn)行dfs均返回d1+1=1，所以對(duì)于4dfs的結(jié)果是d1=1，d2=1，返回給2的值為2，所以最終2dfs結(jié)果是d1=2，d2=2，此時(shí)得到ans最大值：d1+d2=4.返回給結(jié)點(diǎn)1的值為d1+1=3，所以對(duì)1dfs完畢得到的結(jié)果是d1=3，d2=0，最終返回的結(jié)果為d1+1=4，同時(shí)保留答案ans=4文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-704674.html
最后再提示一下，雖然樹的本質(zhì)是無(wú)向圖，但是在建立邊的時(shí)候，直接建成從上往下指的有向邊即可，因?yàn)閐fs的時(shí)候是從上往下的。當(dāng)然建立成無(wú)向邊也可以，只不過需要一個(gè)bool數(shù)組標(biāo)記已經(jīng)遍歷過的結(jié)點(diǎn)，防止進(jìn)入無(wú)限循環(huán)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-704674.html
滿分代碼
#include<iostream>
#include<cstring>
using namespace std;
const int N=20010;
int e[N],ne[N],h[N],idx;
int n,m;
int ans;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u)
{
int d1=0,d2=0;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
int d=dfs(j);
if(d>=d1)d2=d1,d1=d;
else if(d>=d2)d2=d;
}
ans=max(ans,d1+d2);
return d1+1;
}
int main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
for(int i=2;i<=n+m;i++)
{
int x;
scanf("%d",&x);
add(x,i);
}
dfs(1);
cout<<ans;
return 0;
}到了這里，關(guān)于【ccf-csp題解】第四次csp認(rèn)證-第四題-網(wǎng)絡(luò)延時(shí)-樹的直徑的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
