#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=a; i<b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 100000000000000000LL
ll insig;
#define In(vecBRO, LENBRO) REP(IBRO,0,LENBRO) {cin>>insig; vecBRO.pb(insig);}
void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
ll ans; ll K; vector<ll> f_ans;
class SucPath
{
public:
ll N;
vector<ll> fo;
vector<vector<ll> > f2; //sparse table of steps powers of 2
ll ms; //max_steps
SucPath() {N=0LL;}
SucPath(vector<ll> x, ll max_steps)
{
N=x.size(); fo=x; ms=max_steps;
vector<ll> xx;
REP(i,0,(ll) (floor(log2(ms)))+1LL) {xx.pb(0LL);}
REP(i,0,N) {f2.pb(xx);}
Conf2(0);
}
void Conf2(ll e) //O(NlogN)
{
if((1LL<<e)>ms) {return;}
if(e==0) {REP(i,0,N) {f2[i][e]=fo[i];} Conf2(e+1);}
else
{
REP(i,0,N)
{
f2[i][e]=f2[f2[i][e-1]][e-1];
}
}
Conf2(e+1);
}
ll f(ll x,ll s) //O(logN)
{
ll ind=0;
while(s>0)
{
if(s%2!=0) {x=f2[x][ind];}
s/=2; ind++;
}
return x;
}
pl cycle() //Floyd's Algorithm, O(N) time, O(1) memory, return <element of cycle,length od cycle>
{
ll a=fo[0]; ll b=fo[fo[0]];
while(a!=b) {a=fo[a]; b=fo[fo[b]];}
ll l=1; b=fo[a];
while(b!=a) {b=fo[b]; l++;}
return mp(a,l);
}
};
class SparseTable //Range Minimum Queries
{
public:
ll N;
vector<pl> a;
vector<vector<pl> > v;
SparseTable() {N=0LL;}
SparseTable(vector<pl> b)
{
a=b; N=a.size();
ll lo=(ll) floor((double) log2(N)) +1LL;
vector<pl> xx;
REP(i,0,lo) {xx.pb(mp(INF,INF));} REP(i,0,N) {v.pb(xx);}
REP(step,0LL,lo)
{
REP(i,0,N-(1LL<<step)+1LL)
{
if(step==0) {v[i][0]=a[i];}
else {v[i][step]=min(v[i][step-1],v[i+(1LL<<(step-1))][step-1]);}
}
}
}
pl query(ll l, ll r)
{
ll step=(ll) floor((double) log2(r-l+1LL));
return min(v[l][step],v[r-(1LL<<step)+1LL][step]);
}
};
class Tree
{
public:
ll N;
vector<ll> p;
vector<vector<ll> > sons;
vector<vector<ll> > adj;
vector<ll> level;
vector<set<ll> > sonsset;
ll root;
vector<bool> visited;
vector<ll> val; //node values
Tree() {N=0LL;}
Tree(vector<vector<ll> > ad, ll r)
{
N=ad.size(); root=r; adj=ad;
set<ll> xxx; REP(i,0,N) {sonsset.pb(xxx);}
REP(i,0,N) {visited.pb(false); level.pb(0LL);}
vector<ll> xx; REP(i,0,N) {sons.pb(xx); p.pb(-1);;}
DFS_Build(r,r);
REP(i,0,N) {REP(j,0,sons[i].size()) {sonsset[i].insert(sons[i][j]);}}
}
void Reset()
{
REP(i,0,N) {visited[i]=false;}
}
void DFS_Build(ll s, ll par)
{
p[s]=par;
if(s!=root) {level[s]=level[par]+1LL;}
visited[s]=true;
REP(i,0,adj[s].size())
{
if(adj[s][i]==par) {continue;}
sons[s].pb(adj[s][i]);
DFS_Build(adj[s][i],s);
}
return;
}
void DFS(ll s, ll curd, ll las)
{
if(curd<=K) {visited[s]=true;} else {return;}
REP(i,0,sons[s].size())
{
if(sons[s][i]!=las) {DFS(sons[s][i], curd+val[sons[s][i]],s);}
}
if(p[s]!=las) {DFS(p[s],curd+val[s],s);}
}
};
Tree H;
class WTree
{
public:
ll N;
vector<ll> p;
vector<vector<pl> > sons;
vector<vector<pl> > adj;
ll root;
vector<ll> level; //starting in 0
WTree(vector<vector<pl> > ad, ll r)
{
N=ad.size(); root=r; adj=ad;
vector<pl> xx; REP(i,0,N) {sons.pb(xx); p.pb(-1); level.pb(0);}
DFS_Build(r,r);
}
void DFS_Build(ll s, ll par)
{
if(s!=root) {level[s]=level[par]+1LL;}
p[s]=par;
REP(i,0,adj[s].size())
{
if(adj[s][i].ff==par) {continue;}
sons[s].pb(adj[s][i]);
DFS_Build(adj[s][i].ff,s);
}
return;
}
void DFS(ll s)
{
REP(i,0,sons[s].size())
{
DFS(sons[s][i].ff);
}
}
Tree Conv()
{
vector<vector<ll> > ad; vector<ll> xx; REP(i,0,N) {ad.pb(xx);}
vector<ll> values; REP(i,0,N) {values.pb(0LL);}
REP(i,0,N) {REP(j,0,adj[i].size()) {if(adj[i][j].ff==p[i]) {values[i]=adj[i][j].ss;} ad[i].pb(adj[i][j].ff);}}
Tree T(ad,root); T.val=values;
return T;
}
};
void Sub(vector<bool> v, ll k)
{
if(k==v.size())
{
ll N=v.size();
ll susize=0LL;
REP(i,0,N)
{
if(!v[i]) {continue;}
susize++;
H.DFS(i,0LL,-1LL);
}
bool done=true; REP(i,0,N) {if(!H.visited[i]) {done=false;}}
H.Reset();
if(done)
{
if(susize<ans)
{
ans=susize;
f_ans.clear();
REP(i,0,N) {if(v[i]) {f_ans.pb(i+1);}}
}
}
}
else
{
Sub(v,k+1LL);
v[k]=true;
Sub(v,k+1LL);
v[k]=false;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll N; cin>>N>>K; pl cur; ll we; vector<pl> xx; vector<vector<pl> > adj; REP(i,0,N) {adj.pb(xx);}
REP(i,0,N-1)
{
cin>>cur.ff>>cur.ss>>we; cur.ff--; cur.ss--;
adj[cur.ff].pb(mp(cur.ss,we)); adj[cur.ss].pb(mp(cur.ff,we));
}
WTree T(adj,0);
H=T.Conv();
bool task1=true; if(K>20LL) {task1=false;}
REP(i,1,N) {if(H.val[i]<30LL) {task1=false;}}
if(task1) {cout<<N<<endl; REP(i,0,N) {cout<<i+1<<" ";} cout<<endl; return 0;}
bool task4=true;
if(K>30LL) {task4=false;}
REP(i,1,N) {if(H.val[i]<20LL) {task4=false;}}
if(task4)
{
vector<ll> ans;
unordered_map<ll,vector<ll> > m;
ll ml=0LL;
REP(i,0,N) {m[H.level[i]].pb(i); ml=max(ml,H.level[i]);}
vector<bool> v; REP(i,0,N) {v.pb(true);}
for(ll lev=ml;lev>0;lev--)
{
REP(i,0,m[lev].size())
{
ll node=m[lev][i];
if(!v[node]) {continue;}
if(H.val[node]>K) {ans.pb(node); v[node]=false;}
else
{
ll par=H.p[node];
ans.pb(par);
REP(j,0,H.sons[par].size())
{
if(H.val[H.sons[par][j]]<=K) {v[H.sons[par][j]]=false;}
}
v[par]=false;
if(H.val[par]<=K) {v[H.p[par]]=false;}
}
}
}
if(v[0]) {ans.pb(0);}
cout<<ans.size()<<endl;
REP(i,0,ans.size()) {cout<<ans[i]+1<<" ";}
cout<<endl;
return 0;
}
ans=N+1; vector<bool> dummy; REP(i,0,N) {dummy.pb(false);}
H.Reset();
Sub(dummy,0LL);
cout<<ans<<endl;
Out(f_ans);
return 0;
}
Compilation message
Firefighting.cpp: In function 'void Out(std::vector<long long int>)':
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
28 | void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
| ~~~~~~~~~~~~
Firefighting.cpp:28:25: note: in expansion of macro 'REP'
28 | void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
| ^~~
Firefighting.cpp: In constructor 'Tree::Tree(std::vector<std::vector<long long int> >, ll)':
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
136 | REP(i,0,N) {REP(j,0,sons[i].size()) {sonsset[i].insert(sons[i][j]);}}
| ~~~~~~~~~~~~~~~~~~
Firefighting.cpp:136:21: note: in expansion of macro 'REP'
136 | REP(i,0,N) {REP(j,0,sons[i].size()) {sonsset[i].insert(sons[i][j]);}}
| ^~~
Firefighting.cpp: In member function 'void Tree::DFS_Build(ll, ll)':
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
149 | REP(i,0,adj[s].size())
| ~~~~~~~~~~~~~~~~~
Firefighting.cpp:149:9: note: in expansion of macro 'REP'
149 | REP(i,0,adj[s].size())
| ^~~
Firefighting.cpp: In member function 'void Tree::DFS(ll, ll, ll)':
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
161 | REP(i,0,sons[s].size())
| ~~~~~~~~~~~~~~~~~~
Firefighting.cpp:161:9: note: in expansion of macro 'REP'
161 | REP(i,0,sons[s].size())
| ^~~
Firefighting.cpp: In member function 'void WTree::DFS_Build(ll, ll)':
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
192 | REP(i,0,adj[s].size())
| ~~~~~~~~~~~~~~~~~
Firefighting.cpp:192:9: note: in expansion of macro 'REP'
192 | REP(i,0,adj[s].size())
| ^~~
Firefighting.cpp: In member function 'void WTree::DFS(ll)':
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
203 | REP(i,0,sons[s].size())
| ~~~~~~~~~~~~~~~~~~
Firefighting.cpp:203:9: note: in expansion of macro 'REP'
203 | REP(i,0,sons[s].size())
| ^~~
Firefighting.cpp: In member function 'Tree WTree::Conv()':
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
213 | REP(i,0,N) {REP(j,0,adj[i].size()) {if(adj[i][j].ff==p[i]) {values[i]=adj[i][j].ss;} ad[i].pb(adj[i][j].ff);}}
| ~~~~~~~~~~~~~~~~~
Firefighting.cpp:213:21: note: in expansion of macro 'REP'
213 | REP(i,0,N) {REP(j,0,adj[i].size()) {if(adj[i][j].ff==p[i]) {values[i]=adj[i][j].ss;} ad[i].pb(adj[i][j].ff);}}
| ^~~
Firefighting.cpp: In function 'void Sub(std::vector<bool>, ll)':
Firefighting.cpp:221:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
221 | if(k==v.size())
| ~^~~~~~~~~~
Firefighting.cpp: In function 'int main()':
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
279 | REP(i,0,m[lev].size())
| ~~~~~~~~~~~~~~~~~
Firefighting.cpp:279:13: note: in expansion of macro 'REP'
279 | REP(i,0,m[lev].size())
| ^~~
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
288 | REP(j,0,H.sons[par].size())
| ~~~~~~~~~~~~~~~~~~~~~~
Firefighting.cpp:288:21: note: in expansion of macro 'REP'
288 | REP(j,0,H.sons[par].size())
| ^~~
Firefighting.cpp:17:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | #define REP(i,a,b) for(ll i=a; i<b; i++)
......
299 | REP(i,0,ans.size()) {cout<<ans[i]+1<<" ";}
| ~~~~~~~~~~~~~~
Firefighting.cpp:299:9: note: in expansion of macro 'REP'
299 | REP(i,0,ans.size()) {cout<<ans[i]+1<<" ";}
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
907 ms |
178724 KB |
Output is correct |
| 2 |
Correct |
891 ms |
178724 KB |
Output is correct |
| 3 |
Correct |
270 ms |
64164 KB |
Output is correct |
| 4 |
Correct |
901 ms |
174312 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
345 ms |
516 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
47 ms |
364 KB |
Output is correct |
| 6 |
Correct |
28 ms |
364 KB |
Output is correct |
| 7 |
Correct |
62 ms |
364 KB |
Output is correct |
| 8 |
Correct |
314 ms |
492 KB |
Output is correct |
| 9 |
Correct |
147 ms |
492 KB |
Output is correct |
| 10 |
Correct |
147 ms |
492 KB |
Output is correct |
| 11 |
Correct |
155 ms |
364 KB |
Output is correct |
| 12 |
Correct |
80 ms |
364 KB |
Output is correct |
| 13 |
Correct |
58 ms |
364 KB |
Output is correct |
| 14 |
Correct |
8 ms |
364 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
492 KB |
Output is correct |
| 2 |
Correct |
43 ms |
364 KB |
Output is correct |
| 3 |
Correct |
72 ms |
364 KB |
Output is correct |
| 4 |
Correct |
24 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
88 ms |
364 KB |
Output is correct |
| 10 |
Correct |
130 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
56 ms |
364 KB |
Output is correct |
| 13 |
Correct |
36 ms |
364 KB |
Output is correct |
| 14 |
Correct |
42 ms |
364 KB |
Output is correct |
| 15 |
Correct |
92 ms |
364 KB |
Output is correct |
| 16 |
Correct |
47 ms |
364 KB |
Output is correct |
| 17 |
Correct |
159 ms |
408 KB |
Output is correct |
| 18 |
Correct |
93 ms |
364 KB |
Output is correct |
| 19 |
Correct |
109 ms |
492 KB |
Output is correct |
| 20 |
Correct |
275 ms |
492 KB |
Output is correct |
| 21 |
Correct |
203 ms |
492 KB |
Output is correct |
| 22 |
Correct |
369 ms |
492 KB |
Output is correct |
| 23 |
Correct |
189 ms |
492 KB |
Output is correct |
| 24 |
Correct |
46 ms |
364 KB |
Output is correct |
| 25 |
Correct |
56 ms |
364 KB |
Output is correct |
| 26 |
Correct |
86 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
875 ms |
178804 KB |
Output is correct |
| 2 |
Correct |
486 ms |
100852 KB |
Output is correct |
| 3 |
Correct |
490 ms |
103412 KB |
Output is correct |
| 4 |
Correct |
408 ms |
90792 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
865 ms |
176288 KB |
Output is correct |
| 8 |
Correct |
834 ms |
177176 KB |
Output is correct |
| 9 |
Correct |
853 ms |
177060 KB |
Output is correct |
| 10 |
Correct |
861 ms |
177188 KB |
Output is correct |
| 11 |
Correct |
920 ms |
179044 KB |
Output is correct |
| 12 |
Correct |
586 ms |
117020 KB |
Output is correct |
| 13 |
Correct |
336 ms |
72596 KB |
Output is correct |
| 14 |
Correct |
591 ms |
112852 KB |
Output is correct |
| 15 |
Correct |
681 ms |
134896 KB |
Output is correct |
| 16 |
Correct |
760 ms |
144572 KB |
Output is correct |
| 17 |
Correct |
633 ms |
123996 KB |
Output is correct |
| 18 |
Correct |
598 ms |
121904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3065 ms |
2480 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1192 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
