Submission #1320473

#TimeUsernameProblemLanguageResultExecution timeMemory
1320473samarthkulkarniFirefighting (NOI20_firefighting)C++20
3 / 100
413 ms30772 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define vi vector<long long>
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pr pair<ll, ll>
#define ff first
#define ss second

void solution();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}


const int N = 3e5+10;
vector<pr> adj[N];
ll sz[N];
bool vis[N];
bool safe[N];
ll n, k;
vi res;

ll get_sz(int a, int p) {
	sz[a] = 0;
	for (auto [b, w] : adj[a]) {
		if (vis[b] || safe[b] || b == p) continue;
		sz[a] = max(sz[a], w + get_sz(b, a));
	}
	return sz[a];
}

int centroid(int a, int p, ll l) {
	for (auto [b, w] : adj[a]) {
		if (!vis[b] && !safe[b] && b != p && sz[b]*2 > l) 
			return centroid(b, a, l);
	}
	return a;
}


void add_safe(int a, int p, ll d) {
	if (d > k) return;
	safe[a] = true;
	for (auto [b, w] : adj[a]) {
		if (vis[b] || safe[b] || b == p) continue;
		add_safe(b, a, d+w);
	}
}


void solve(int a, int p) {
	int c = centroid(a, p, get_sz(a, p));

	vis[c] = true;
	if (!safe[c]) {
		res.push_back(c);
		safe[c] = true;
		for (auto [b, w] : adj[c]) {
			if (vis[b] || safe[b]) continue;
			add_safe(b, c, w);
		}
	} 

	
	for (auto [b, w] : adj[c]) {
		if (vis[b]) continue; 
		solve(b, c);
	}
}



void solution() {
	cin >> n >> k;

	for (int i = 1; i < n; i++) {
		ll a, b, w;
		cin >> a >> b >> w;
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
	}

	solve(1, 1);
	cout << res.size() << endl;
	for (auto val : res) cout << val << " ";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...