結果

問題 No.1752 Up-Down Tree
ユーザー HanghangHanghang
提出日時 2024-06-04 15:35:34
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,351 bytes
コンパイル時間 5,691 ms
コンパイル使用メモリ 195,368 KB
実行使用メモリ 65,792 KB
最終ジャッジ日時 2024-06-04 15:35:44
合計ジャッジ時間 9,289 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 151 ms
65,664 KB
testcase_01 AC 126 ms
65,792 KB
testcase_02 AC 96 ms
59,632 KB
testcase_03 AC 96 ms
59,760 KB
testcase_04 AC 118 ms
62,720 KB
testcase_05 AC 121 ms
63,872 KB
testcase_06 AC 120 ms
61,684 KB
testcase_07 AC 119 ms
61,684 KB
testcase_08 AC 95 ms
53,376 KB
testcase_09 WA -
testcase_10 RE -
testcase_11 WA -
testcase_12 AC 22 ms
50,432 KB
testcase_13 AC 64 ms
53,376 KB
testcase_14 AC 77 ms
54,016 KB
testcase_15 AC 31 ms
51,328 KB
testcase_16 AC 93 ms
53,760 KB
testcase_17 AC 62 ms
53,248 KB
testcase_18 AC 122 ms
57,088 KB
testcase_19 AC 121 ms
57,088 KB
testcase_20 AC 22 ms
50,304 KB
testcase_21 AC 21 ms
50,432 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/priority_queue.hpp>
#define heap __gnu_pbds::priority_queue 

typedef long long ll;
const int N=1e6+3;
int n,f[N],sz[N],val[N],dep[N];
vector<int>ve[N];
struct Nod{int x,id;};
bool operator <(Nod A,Nod B)
{
    if(A.x!=B.x)return A.x<B.x;
	if(val[A.id]!=val[B.id])return val[A.id]<val[B.id];
	return dep[A.id]<dep[B.id];
}
heap<Nod>q[N];
bool ban[N],leaf[N];
void Dfs(int x,int fa)
{
	if(ve[x].size()==1&&fa){f[x]=1;q[x].push({1,x});return;}
	for(int y:ve[x])if(y!=fa)Dfs(y,x),q[x].join(q[y]);
	if(q[x].size()==1){f[x]=q[x].top().x;if(x>1)q[x].push({1,x});return;}
	f[x]=1+q[x].top().x;q[x].pop();
	f[x]+=q[x].top().x;q[x].pop();
	if(x>1)q[x].push({f[x],x});
}
void Sz(int x,int fa)
{
	sz[x]=ban[x]==0;
	for(int y:ve[x])if(y!=fa)Sz(y,x),sz[x]+=sz[y];
}
void Pre(int x,int fa)
{
	dep[x]=dep[fa]+1;
	if(ve[x].size()==1&&fa){leaf[x]=1;return;}
	for(int y:ve[x])if(y!=fa)Pre(y,x);
	if(ve[x].size()==2)
	{
		if(leaf[ve[x][0]])val[x]=-1,val[ve[x][0]]=1;
		if(leaf[ve[x][1]])val[x]=-1,val[ve[x][1]]=1;
	}
}
int main()
{
	cin>>n;
	for(int i=1,x,y;i<n;i++)cin>>x>>y,ve[x].push_back(y),ve[y].push_back(x);
	Pre(1,0);Dfs(1,0);
	while(q[1].size())ban[q[1].top().id]=1,q[1].pop();
	Sz(1,0);
	for(int i=1;i<=n;i++)if(ban[i]&&sz[i]){f[1]++;break;}
	cout<<f[1];
}
0