#include#include#includeusingnamespacestd;intN,V[10100];vectorson[10100];//圖intMAX[10100],MAXN[10100];//最大值及其標號intSMAX[10100],SMAXN[10100];//次大值及其標號boolvis[10100];//標" />

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

hdu2196Computer 經典樹形dp 在樹上求最長距離

系統 2356 0

hdu2196

題解

兩次搜索的方法

?

    #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 

*/
  


?

?

hdu2196Computer 經典樹形dp 在樹上求最長距離


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 亚洲艹逼 | 天天翘夜夜洗澡天天做 | 九草在线免费观看 | 欧美视频成人 | 久久夜色视频 | 久久乐国产综合亚洲精品 | 2021精品综合久久久久 | 毛片大全在线 | 日韩中文字幕视频在线 | 久青草视频免费观看青 | 毛片不卡一区二区三区 | 99r8这里精品热视频免费看 | 国产在线公开视频 | 成年性视频bbixx | 日本人xx视频免费视频 | 成人在线不卡视频 | 波多野结衣一区二区三区 | 国产一区二区三区久久精品 | 中文字幕51精品乱码在线 | 越南黄色录像 | 福利视频区 | 四虎最新永久免费视频 | 95视频在线观看在线分类h片 | 大乳妇女bd视频在线观看 | 爱性网| 乱码一区二区三区完整视频 | 欧美成人aa大片拍拍拍 | 四虎永久免费在线观看 | 国产―笫一页―浮力影院xyz | 日韩欧美一二三 | 久久99热久久精品 | 久草这里只有精品 | 国产精品日韩欧美久久综合 | 中国一级毛片 | 亚洲欧美日韩综合在线 | 青青久久久 | 国产精品成人观看视频免费 | 最新国产福利 | 一本色道久久综合狠狠躁 | 国产精品免费播放 | 中文字幕日韩精品麻豆系列 |