結果

問題 No.1752 Up-Down Tree
ユーザー HanghangHanghang
提出日時 2024-06-04 15:41:24
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 1,764 bytes
コンパイル時間 3,277 ms
コンパイル使用メモリ 176,156 KB
実行使用メモリ 28,288 KB
最終ジャッジ日時 2024-06-04 15:41:31
合計ジャッジ時間 5,488 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 93 ms
28,288 KB
testcase_01 AC 67 ms
28,160 KB
testcase_02 AC 65 ms
23,584 KB
testcase_03 AC 70 ms
23,588 KB
testcase_04 AC 69 ms
25,916 KB
testcase_05 AC 98 ms
26,752 KB
testcase_06 AC 72 ms
25,012 KB
testcase_07 AC 71 ms
25,012 KB
testcase_08 AC 31 ms
14,464 KB
testcase_09 AC 91 ms
27,068 KB
testcase_10 RE -
testcase_11 AC 9 ms
10,624 KB
testcase_12 AC 5 ms
10,496 KB
testcase_13 AC 36 ms
16,512 KB
testcase_14 AC 46 ms
17,600 KB
testcase_15 AC 13 ms
12,032 KB
testcase_16 AC 41 ms
17,344 KB
testcase_17 AC 35 ms
16,060 KB
testcase_18 AC 97 ms
24,252 KB
testcase_19 AC 85 ms
24,064 KB
testcase_20 AC 7 ms
10,624 KB
testcase_21 AC 6 ms
10,752 KB
権限があれば一括ダウンロードができます

ソースコード

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