[TJOI 2017] 도시 나무 dp+나무의 직경+나무의 중심

원제:https://www.luogu.org/problemnew/show/P3761
문제풀이: 가장 긴 체인을 가장 짧게 하기 위해 가장자리를 수정합니다.각 변을 열거하면 분명히 나무를 두 개의 연결 블록으로 나눌 수 있다. 그러면 가장 긴 체인은 두 개의 연결 블록의 직경일 수도 있고, 두 개의 연결 블록을 연결하는 중심, 즉 두 개의 나무를 연결하는 반경+열거의 변길이일 수도 있다.트리 dp로 구할 수 있습니다.
지름의 경우:

dp[x][0/1]를 설정하면 x를 뿌리 나무의 최대 길이와 차대 길이

를 나타낸다

void getd(int x,int &ans){
	
	for(int i=h[x];i;i=data[i].nxt){
		int y=data[i].to;int c=data[i].w;if(vis[y]) continue;
		vis[y]=1;getd(y,ans);
		if(dp[y][0]+c>dp[x][0]){//    
			dp[x][1]=dp[x][0];son[x]=y;
			dp[x][0]=dp[y][0]+c;
		}else if(dp[y][0]+c>dp[x][1]){//   
			dp[x][1]=dp[y][0]+c;
		} 
	} 
	ans=max(ans,dp[x][0]+dp[x][1]);
}

중심과 반지름의 경우:

from[x]는 x를 뿌리로 하는 자수를 제외하고 다른 점에서 x까지의 최장거리

를 나타낸다

뿌리에서 밀어냄

void getr(int x,int from,int &ans){
	ans=min(ans,max(dp[x][0],from));
	for(int i=h[x];i;i=data[i].nxt){
		int y=data[i].to;int c=data[i].w;
		if(!vis[y]) continue;
		vis[y]=0;
		if(son[x]==y) getr(y,max(dp[x][1],from)+c,ans);
		else getr(y,max(dp[x][0],from)+c,ans);
	}
}

#include
#define inf (1<<30)-1
using namespace std;
const int N=5500;
int dp[N][2];
int n,len=1;
struct E{
	int to,w,nxt;
}data[N<<1];
int u[N],v[N],val[N],h[N],son[N];
bool vis[N];
int d1,d2,r1,r2,ans;
inline int rd(){
	int x=0;int f=1;char s=getchar();
	while(!isdigit(s)) f=(s=='-'?-1:f),s=getchar();
	while(isdigit(s)) x=(x<<1)+(x<<3)+s-'0',s=getchar();
	return x*f;
}
inline void ins(int x,int y,int w){
	data[++len].to=y;data[len].w=w;data[len].nxt=h[x];h[x]=len;
	data[++len].to=x;data[len].w=w;data[len].nxt=h[y];h[y]=len;
}
inline void clear(){
	memset(dp,0,sizeof dp);
	memset(vis,0,sizeof vis); 
	memset(son,0,sizeof son);
} 

void getd(int x,int &ans){
	
	for(int i=h[x];i;i=data[i].nxt){
		int y=data[i].to;int c=data[i].w;if(vis[y]) continue;
		vis[y]=1;getd(y,ans);
		if(dp[y][0]+c>dp[x][0]){//    
			dp[x][1]=dp[x][0];son[x]=y;
			dp[x][0]=dp[y][0]+c;
		}else if(dp[y][0]+c>dp[x][1]){
			dp[x][1]=dp[y][0]+c;
		} 
	} 
	ans=max(ans,dp[x][0]+dp[x][1]);
}
void getr(int x,int from,int &ans){
	ans=min(ans,max(dp[x][0],from));
	for(int i=h[x];i;i=data[i].nxt){
		int y=data[i].to;int c=data[i].w;
		if(!vis[y]) continue;
		vis[y]=0;
		if(son[x]==y) getr(y,max(dp[x][1],from)+c,ans);
		else getr(y,max(dp[x][0],from)+c,ans);
	}
}
int main(){
	//freopen("city.in","r",stdin);
	n=rd();
	for(int i=1;i