---
tags: CSES題解
---

CSES Problem Set — Tree Distances I 題解
===

題目
---
給一顆有$n$個節點的樹。
找出每個節點到其他節點的最大距離。

### 輸入
第一行輸入包含一個整數$n$ : 節點的數量。這些節點編號為$1,2,\ldots,n$。
接下來有$n-1$描述邊。每一行包含兩個整數$a$和$b$ : 點$a$和$b$間有一條邊。

### 輸出
輸出$n$個整數 : 所有節點$1,2,\ldots,n$到其他點的最大距離。

想法
---
根據樹直徑那題所說，每個節點的最遠點必是樹直徑的其中一端。
因此對兩個直徑端點分別``DFS``，對每個節點來說，其中一個端點會是他的最遠點，從直徑兩端``DFS``時對每個節點距離取``max``即可。

範例程式碼
---

#include<bits/stdc++.h>
using namespace std;

int cnt=1;
vector<int> Head(200500,0);
vector<int> Next(400500);
vector<int> To(400500);
vector<int> maxdis(200500,0);
void addEdge(int u,int v){
    Next[cnt]=Head[u];
    To[cnt]=v;
    Head[u]=cnt++;
}
/*************鍊式前向星建圖****************/

int farn;
int maxd=-1;

//找出直徑兩端
void dfs(int u,int par,int dis){
	if(dis>maxd){
		maxd=dis;
		farn=u;
	}
	for(int e=Head[u];e;e=Next[e]){
        int x=To[e];
		if(x!=par){
			dfs(x,u,dis+1);
		}
	}
}

//更新每個點的最大距離
void dfs2(int u,int par,int dis){
	maxdis[u]=max(maxdis[u],dis);
	for(int e=Head[u];e;e=Next[e]){
        int x=To[e];
		if(x!=par){
			dfs2(x,u,dis+1);
		}
	}
}

int main(){
	int n;
	cin>>n;
	for(int i=0;i<n-1;i++){
		int a,b;
		cin>>a>>b;
		addEdge(a,b);
        addEdge(b,a);
	}
    
    //找出直徑兩個端點
	dfs(1,0,0);
	maxd=-1;
	int start=farn;
	dfs(farn,0,0);
    
    //從直徑兩端分別DFS
	dfs2(farn,0,0); 
	dfs2(start,0,0);
	for(int i=1;i<=n;i++)
		cout<<maxdis[i]<<" \n"[i==n];
	return 0;
}