Tree - Height of a Tree - sinapusu2002 @ ウィキ

Tree - Height of a Tree
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_B&lang=jp

木を２回精査すれば簡単です。
木を２往復するので計算量はＢｉｇＯ（２*頂点数）です。

速すぎて一位タイです。
これ以上シンプルな考え方もないし計算に必要なデータを集めるのに最初の１周。
確定するのにもう一周必要なので、私の発想は理論値でしょう。
多分コード実行速度一位の方と同じ発想になってると思います。

着想を得るのに１０分かかりました。
実装するとき考え抜けに気付かず１時間かかりました。
テストに20分かかりました（コードの修正）。

木の根元を点0として枝先から根元へ向かう計算に一周目を。
点0から枝先に向かう計算で２周目を使います。

例えば木を一周した結果根元で14,17,22という高さになる枝が３つ出ていたら。
14や17に向かう時は22を最大として２周目を回ればいいですし。
２２の枝先に向かう時は17を最大として２周目の２２の先の枝先を回ればいいわけです。

#include<stdio.h>
#include<map>
#include<string.h>
#include<queue>
#include<set>
#include<algorithm>


const int LIMIT=10000;
std::map<int,int> tree[LIMIT]; 

int ans[LIMIT];
int maxWs1[LIMIT];
int maxWs2[LIMIT];
int maxPs1[LIMIT];
int maxPs2[LIMIT];

int saiki(int p,int old,int maxW1){
	std::map<int,int>::iterator it;
	int maxW2=0;
	int maxP1=old;
	int maxP2=-1;
		
	for(it=tree[p].begin();it!=tree[p].end();it++){
		if((*it).first==old)continue;
		int temp=saiki((*it).first,p,maxW1+(*it).second);
		if(temp>=maxW1){
			maxP2=maxP1;
 			maxP1=(*it).first;
			maxW2=maxW1;
			maxW1=temp;
		}else if(temp>=maxW2){
			maxW2=temp;
			maxP2=maxP1;
		}
	}
	maxPs1[p]=maxP1;
	maxPs2[p]=maxP2;
	maxWs1[p]=maxW1;
	maxWs2[p]=maxW2;
	ans[p]=maxW1;
	if(old==maxP1){
		return maxW2+tree[p][old];
	}else{
		return maxW1+tree[p][old];
	}
} 
void saiki2(int p,int old,int maxW){
 	std::map<int,int>::iterator it;
	for(it=tree[p].begin();it!=tree[p].end();it++){
		if((*it).first==old)continue;
		int nextP=(*it).first;
 		int temp;
		if(nextP==maxPs1[p]){
			saiki2(nextP,p,std::max(maxWs2[p],maxW)+(*it).second);
		}else{
			saiki2(nextP,p,std::max(maxWs1[p],maxW)+(*it).second);
		}
 	}
	ans[p]=std::max(ans[p],maxW);
	
}

int main(){
	int n;
	scanf("%d",&n);
	memset(ans,0,sizeof(ans));
	memset(maxWs1,0,sizeof(maxWs1));
	memset(maxWs2,0,sizeof(maxWs2));
	for(int i=0;i<n-1;i++){
		int s,t,w;
		scanf("%d %d %d",&s,&t,&w);
		tree[s][t]=w;
 		tree[t][s]=w;
	}
	saiki(0,-1,0);
	saiki2(0,-1,0);
	for(int i=0;i<n;i++)printf("%d\n",ans[i]);
}