結果

問題 No.1752 Up-Down Tree
コンテスト
ユーザー Hanghang
提出日時 2024-06-04 15:41:24
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,764 bytes
コンパイル時間 2,082 ms
コンパイル使用メモリ 178,064 KB
実行使用メモリ 28,288 KB
最終ジャッジ日時 2024-12-23 10:56:14
合計ジャッジ時間 4,236 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

# include <bits/stdc++.h>
# define fir first
# define sec second
# define mp std::make_pair

const int N=100010,INF=0x3f3f3f3f;

inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-') f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
int n;
int f[N];
std::vector <int> G[N];

void init(int x,int fa){
	f[x]=fa;
	for(auto y:G[x]) if(y!=fa) init(y,x);
	return;
}

std::multiset <std::pair <int,int> > S[N];
int ans;

// int fmax[N];
// do not consider last step up.

void solve(int x){
	if(f[x]&&G[x].size()==1){
		S[x].insert(mp(1,0));
		return;
	}
	
	int id=0;
	
	for(auto y:G[x]){
		if(y==f[x]) continue;
		solve(y);
		if(S[id].size()<S[y].size()) id=y;
//		for(auto v:S[y]) S[x].insert(v);
	}
	
	S[x].swap(S[id]);
	for(auto y:G[x]){
		if(y==f[x]||y==id) continue;
		for(auto v:S[y]) S[x].insert(v);
	}
	
	ans=std::max(ans,(*S[x].rbegin()).fir+(*S[x].rbegin()).sec);
	if(S[x].size()!=1){
		auto it=S[x].end();
		auto u=--it;
		auto v=--it;
		int w=(*u).fir+(*v).fir,k=(*u).sec|(*v).sec;
		
//		printf("u = %d %d v = %d %d\n",(*u).fir,(*u).sec,(*v).fir,(*v).sec);
		
		if(*v==mp(1,0)&&(*u).sec==1){
			if(it==S[x].begin()) k=0;
		}
		S[x].erase(u),S[x].erase(v),S[x].insert(mp(w+1,k));
		ans=std::max(ans,w+1+k);
	}else{
		auto it=*S[x].begin();
		S[x].clear();
		S[x].insert(mp(it.fir,1)),ans=std::max(it.fir+1,ans);
		S[x].insert(mp(1,0));
	}
	
	// printf("at %d:",x);
	// for(auto v:S[x]) printf("(%d,%d) ",v.fir,v.sec);
	// puts("");

	return;
}

int main(void){
//	freopen("bird.in","r",stdin);
//	freopen("bird.out","w",stdout);
	
	n=read();
	
	for(int i=2,u,v;i<=n;++i) u=read(),v=read(),G[u].push_back(v),G[v].push_back(u);
	init(1,0);
	
	solve(1);
	printf("%d",ans);

	return 0;
}
0