| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 737599 | Ronin13 | Firefighting (NOI20_firefighting) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 300001;
vector <vector <pll> > g(nmax);
int p[nmax][22];
ll d[nmax][22];
//ll len[nmax][22];
ll dp[nmax];
vector <vector <pll> > cent(nmax);
vector <ll> cur(nmax);
void dfs(int v, int e, ll last){
p[v][0] = e;
d[v][0] = last;
for(int j = 1; j <= 20; j++){
p[v][j] = p[p[v][j - 1]][j - 1];
d[v][j] = d[v][j - 1] + d[p[v][j - 1]][j - 1];
}
for(auto x : g[v]){
int to = x.f;
if(to == e) continue;
dp[to] = dp[v] + x.s;
dfs(to, v, x.s);
}
}
ll getlast(int v, ll k){
for(int j = 20; j >= 0; j--){
if(d[v][j] > k) continue;
k -= d[v][j];
v = p[v][j];
}
return v;
}
vector <int> sz(nmax);
vector <bool> marked(nmax);
void DFS(int v, int e){
sz[v] = 1;
for(auto ed : g[v]){
int to = ed.f;
if(to == e) continue;
if(marked[to]) continue;
DFS(to, v);
sz[v] += sz[to];
}
}
int find_cen(int v, int e, int n){
for(auto ed : g[v]){
int to = ed.f;
if(to == e) continue;
if(marked[to]) continue;
if(sz[to] > n / 2){
return find_cen(to, v, n);
}
}
return v;
}
void DFS2(int v, int e, int lead, ll cur){
cent[v].pb({lead, cur});
for(auto x : g[v]){
int to = x.f;
if(to == e) continue;
if(marked[to]) continue;
DFS2(to, v, lead, cur + x.s);
}
}
void upd(int v){
for(auto to : cent[v]){
cur[to.f] = min(cur[to.f], to.s);
}
}
ll getans(int v){
ll mn = 1e18;
for(auto to : cent[v]){
mn = min(mn, cur[to.f] + to.s);
}
return mn;
}
void decompose(int v){
DFS(v, v);
int x = find_cen(v, v, sz[v]);
DFS2(x, x, x, 0);
marked[x] = true;
for(auto ed : g[x]){
int to = ed.f;
if(marked[to]) continue;
decompose(to);
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int n; cin >> n;
ll k; cin >> k;
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
ll w; cin >> w;
g[u].pb({v, w});
g[v].pb({u, w});
}
for(int j= 0; j < 20; j++){
d[0][j] = 1e12;
}
dfs(1, 1, 0);
decompose(1);
vector <pll> vec;
for(int i= 1;i <= n; i++){
vec.pb({dp[i], i});
}
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());
int cnt = 0;
vector <int> ans;
for(int i = 1; i <= n; i++){
cur[i] = 1e18;
}
for(auto x : vec){
int to = x.s;
ll o = getans(to);
if(o <= k){
continue;
}
cnt++;
int v = getlast(to, k);
upd(v);
ans.pb(v);
}
cout << cnt << "\n";
for(int to : ans){
cout<< to << ' ';
}
return 0;
}