兩次搜索的方法
?
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int N,V[10100];
vector<int>son[10100]; //圖
int MAX[10100],MAXN[10100]; //最大值及其標號
int SMAX[10100],SMAXN[10100]; //次大值及其標號
bool vis[10100]; //標記訪問狀態
void dfs1(int n) //在以n為根節點的子樹上求出節點n到葉子節點距離的最大值
{
MAX[n]=SMAX[n]=0;
int len=son[n].size();
for(int i=0;i<len;i++)
{
int k=son[n][i]; //兒子標號 - -
dfs1(k);
if(SMAX[n]<MAX[k]+V[k])
{
SMAX[n]=MAX[k]+V[k];
SMAXN[n]=k;
if(SMAX[n]>MAX[n]){
swap(SMAX[n],MAX[n]);
swap(SMAXN[n],MAXN[n]);
}
}
}
}
void dfs2(int n) //求出n的兒子們在樹中能延伸的最大距離(n的最大距離及次大距離已得到)
{
int len=son[n].size();
vis[n]=1;
for(int i=0;i<len;i++)
{
int k=son[n][i];
if(vis[k]) continue;
if(k==MAXN[n]){
if(SMAX[k]<SMAX[n]+V[k]){
SMAX[k]=SMAX[n]+V[k];
SMAXN[k]=n;
if(SMAX[k]>MAX[k]){
swap(SMAX[k],MAX[k]);
swap(SMAXN[k],MAXN[k]);
}
}
}
else{
if(SMAX[k]<MAX[n]+V[k]){
SMAX[k]=MAX[n]+V[k];
SMAXN[k]=n;
if(SMAX[k]>MAX[k]){
swap(SMAX[k],MAX[k]);
swap(SMAXN[k],MAXN[k]);
}
}
}
dfs2(k);
}
}
int main()
{
int i,j,k,u,v;
while(scanf("%d",&N)!=EOF)
{
for(i=1;i<=N;i++) son[i].clear();
for(i=2;i<=N;i++){
scanf("%d%d",&u,&V[i]);
son[u].push_back(i); //i的父親是u
}
memset(vis,0,sizeof(vis));
dfs1(1);
// 測試
// for(i=1;i<=N;i++) printf("~%d ",MAX[i]);printf("\n");
// for(i=1;i<=N;i++) printf("~%d ",SMAX[i]);printf("\n");
memset(vis,0,sizeof(vis));
dfs2(1);
for(i=1;i<=N;i++) printf("%d\n",MAX[i]);
}
return 0;
}
/*
5
1 1
2 1
3 1
1 1
*/
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
