結果

問題 No.1928 Make a Binary Tree
コンテスト
ユーザー kotatsugame
提出日時 2022-05-07 02:20:20
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 255 ms / 3,000 ms
コード長 651 bytes
コンパイル時間 679 ms
コンパイル使用メモリ 77,968 KB
実行使用メモリ 47,088 KB
最終ジャッジ日時 2024-07-06 06:07:19
合計ジャッジ時間 8,774 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main()
      | ^~~~

ソースコード

diff #
raw source code 

#include<iostream>
#include<set>
#include<vector>
using namespace std;
int N;
vector<int>G[2<<17];
multiset<int>ret;
int dfs(int u,int p)
{
	int ch=1;
	multiset<int>now;
	for(int v:G[u])if(v!=p)
	{
		int c=dfs(v,u);
		if(now.size()<ret.size())now.swap(ret);
		for(int d:ret)now.insert(d);
		now.insert(c);
	}
	if(!now.empty())
	{
		auto it=now.end();
		it--;
		ch+=*it;
		now.erase(it);
		if(!now.empty())
		{
			auto it=now.end();
			it--;
			ch+=*it;
			now.erase(it);
		}
	}
	ret.swap(now);
	return ch;
}
main()
{
	cin>>N;
	for(int i=1;i<N;i++)
	{
		int u,v;cin>>u>>v;u--,v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	cout<<dfs(0,-1)<<endl;
}
0