結果

問題 No.1752 Up-Down Tree
ユーザー HanghangHanghang
提出日時 2024-06-04 15:36:17
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,265 bytes
コンパイル時間 2,087 ms
コンパイル使用メモリ 195,232 KB
実行使用メモリ 66,048 KB
最終ジャッジ日時 2024-06-04 15:36:27
合計ジャッジ時間 6,209 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 149 ms
66,048 KB
testcase_01 AC 152 ms
65,920 KB
testcase_02 AC 117 ms
59,636 KB
testcase_03 AC 121 ms
59,636 KB
testcase_04 AC 155 ms
63,104 KB
testcase_05 AC 148 ms
64,000 KB
testcase_06 AC 137 ms
62,084 KB
testcase_07 AC 165 ms
62,080 KB
testcase_08 AC 104 ms
53,120 KB
testcase_09 WA -
testcase_10 RE -
testcase_11 WA -
testcase_12 AC 41 ms
50,304 KB
testcase_13 AC 86 ms
53,248 KB
testcase_14 AC 101 ms
54,144 KB
testcase_15 AC 51 ms
51,200 KB
testcase_16 AC 98 ms
53,760 KB
testcase_17 AC 83 ms
53,120 KB
testcase_18 AC 145 ms
56,960 KB
testcase_19 AC 151 ms
57,088 KB
testcase_20 AC 41 ms
50,432 KB
testcase_21 AC 40 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&&fa)val[x]=-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