結果

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

ソースコード

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