結果

問題 No.763 Noelちゃんと木遊び
コンテスト
ユーザー zubassyaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaanMAX
提出日時 2024-07-11 19:28:03
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 74 ms / 2,000 ms
コード長 3,743 bytes
コンパイル時間 3,614 ms
コンパイル使用メモリ 290,396 KB
実行使用メモリ 27,008 KB
最終ジャッジ日時 2025-03-22 10:43:51
合計ジャッジ時間 5,573 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<unordered_set>
#include<cassert>
using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define Rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rep1(i,n) for(int i=1;i<=(n);i++)
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vd = vector<double>;
using vvd = vector<vd>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vl = vector<long long>;
using vvl = vector<vl>;
#define INF ((ll)2e18)
#define IINF ((int)1e9)
const double PI = 3.1415926535897932384626433832795028841971;
template<typename T>inline bool chmax(T& a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T>inline bool chmin(T& a, T b) { return ((a > b) ? (a = b, true) : (false)); }
#define yesno(ans) cout<<(ans?"Yes\n":"No\n")
#define all(v) (v).begin(),(v).end()
const int di[] = { 0, 1, 0,-1 };
const int dj[] = { 1, 0,-1, 0 };
//const int di[] = { 0, 1, 1, 1, 0, -1,-1,-1};
//const int dj[] = { 1, 1, 0,-1,-1, -1, 0, 1};
//const int di[]={-1,-1, 0, 0, 1, 1};
//const int dj[]={-1, 0,-1, 1, 0, 1};
const double EPS = 1e-11;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T& val) {
	std::fill((T*)array, (T*)(array + N), val);
}

int solve1();
int solve2();
/*
#include <random>

std::random_device seed_gen;
std::mt19937 engine(seed_gen());
void generate() {
	int n = engine() %20;
	int s=5*n;

	//int n = 1000;
	cout << n << " "<<s<<endl;

	rep(i, n) {
		cout<<(engine()%212122 * 10282)%10+1<<" ";
		cout<<(engine()%212122 * 10282)%10+1<<endl;
	}
}//*/

int main() {
	std::cin.tie(0)->sync_with_stdio(0);
	//generate();

	int T = 1;
	while (T--)solve1();
	return 0;
}

/*ACL
#include<atcoder/all>
using namespace atcoder;

//using mint = modint998244353;
using mint = modint1000000007;
//using mint = modint;
using vm = vector<mint>;
using vvm = vector<vm>;
using vvvm = vector<vvm>;
//*/

#define MAX 10000000000
//#define MOD 1000000000000037

struct Edge
{
	int to;
	ll cost;
	Edge(int to, ll cost) :to(to), cost(cost) {}

	bool operator<(const Edge Ano)const {
		return cost < Ano.cost;
	}

	bool operator>(const Edge Ano)const {
		return cost > Ano.cost;
	}
};

//木の直径(g:隣接リスト)
ll diameterOfTree(vector<vector<Edge>>g) {
	vector<ll>d(g.size());
	ll ret = 0;

	auto bfs = [&](int s)->void {
		for (int i = 0; i < g.size(); i++)d[i] = INF;
		queue<int>q;
		q.push(s);
		d[s] = 0;
		int u;
		while (!q.empty()) {
			u = q.front(); q.pop();
			for (auto [to,cost] : g[u]) {
				if (d[to] == INF) {
					d[to] = d[u] + cost;
					q.push(to);
				}
			}
		}
	};
	bfs(0);
	ll maxdist = 0;
	int tgt = 0;
	for (int i = 0; i < g.size(); i++) {
		if (d[i] == INF)continue;
		if (maxdist < d[i]) {
			maxdist = d[i];
			tgt = i;
		}
	}
	bfs(tgt);
	for (int i = 0; i < g.size(); i++) {
		if (d[i] == INF)continue;
		ret = max(ret, d[i]);
	}
	return ret;
}

//木の高さの最小値
ll minTreeHigh(vector<vector<Edge>>g) {
	return (diameterOfTree(g) + 1) / 2;
}

//木の最大安定集合
vector<int> maxStableSet(vector<vector<Edge>>g) {
	vector<bool>used(g.size(), false);
	auto dfs = [&](auto dfs, int pos, int par)->void {
		bool exist = false;
		
		for (auto &[to,cost] : g[pos]) {
			if (to == par)continue;
			dfs(dfs,to, pos);
			if (used[to])exist = true;
		}
		if (!exist)used[pos] = true;
	};

	dfs(dfs, 0,-1);
	vector<int> ret(0);
	for (int v = 0; v < g.size(); v++) {
		if (used[v])ret.push_back(v);
	}
	return ret;
}

int solve1() {
	int n; cin >> n;
	vector<vector<Edge>>g(n);
	rep(i, n-1) {
		int a, b; cin >> a >> b;
		a--, b--;
		g[a].emplace_back(b, 1);
		g[b].emplace_back(a, 1);
	}
	cout << maxStableSet(g).size() << endl;
	return 0;
}
0