#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n, k;
ll A[200005];
vector<pll> T[200005];
ll val[200005];
ll Right[200005];
ll Left[200005];
ll dp[200005];
bool done[200005];
ll reroot[200005];
pll ans = mp(INT_MAX , 0);
bool check(ll value)
{
ll cnt = 0;
ll cur = 0;
ll ptr = 1;
for(int i = 1; i<= n; i++)
{
for(; ptr < n; ptr++)
{
if(cur+A[ptr]>value) break;
cur += A[ptr];
}
Right[i] = ptr;
cur-=A[i];
}
ptr = n-1;
cur = 0;
for(int i = n; i>= 1; i--)
{
for(; ptr > 0; ptr--)
{
if(cur+A[ptr]>value) break;
cur += A[ptr];
}
Left[i] = ptr+1;
cur-=A[i-1];
}
ll node = 1, Max = INT_MAX;
for(int i = 1; i<= n; i++)
{
if(Left[i]>node) Max = min(Max, Right[i]);
if(Max==i)
{
cnt++;
node = i;
Max = INT_MAX;
continue;
}
}
if(cnt<=k) return 1;
return 0;
}
void print_ans(ll value)
{
ll cnt = 0;
ll cur = 0;
ll ptr = 1;
for(int i = 1; i<= n; i++)
{
for(; ptr < n; ptr++)
{
if(cur+A[ptr]>value) break;
cur += A[ptr];
}
Right[i] = ptr;
cur-=A[i];
}
ptr = n-1;
cur = 0;
for(int i = n; i>= 1; i--)
{
for(; ptr > 0; ptr--)
{
if(cur+A[ptr]>value) break;
cur += A[ptr];
}
Left[i] = ptr+1;
cur-=A[i-1];
}
vector<ll> save;
ll node = 1, Max = INT_MAX;
for(int i = 1; i<= n; i++)
{
if(Left[i]>node) Max = min(Max, Right[i]);
//cout << Max << " " << i << "\n";
if(Max==i)
{
cnt++;
node = i;
Max = INT_MAX;
save.push_back(i);
continue;
}
}
cout << value << "\n";
for(auto u: save) done[u] = 1;
ll Le = k;
Le -= save.size();
for(int i = 1; i<= n; i++)
{
if(Le==0||done[i]) continue;
done[i] = 1;
Le--;
}
for(int i = 1; i<= n; i++) if(done[i]) cout << i << " ";
}
void solve_large()
{
ll Max = 0;
for(int i = 1; i< n; i++) Max = max(Max, val[i]);
ll lo = 0, hi = 1e16, mid;
while(hi-lo>1)
{
mid = ((hi+lo)>>1);
//cout << lo << " " << hi << "\n";
if(check(mid)) hi = mid;
else lo = mid;
}
ll idx = 0;
if(check(lo)) idx = lo;
else idx = hi;
print_ans(idx);
}
void dfs(ll v, ll par)
{
for(auto u: T[v])
{
if(u.fi==par) continue;
dfs(u.fi , v);
dp[v] = max(dp[v], dp[u.fi]+u.se);
}
//cout << dp[v] << " " << v << "\n";
}
void dfsk(ll v, ll par)
{
vector<pll> save;
ll Max = reroot[v];
for(auto u: T[v])
{
if(u.fi==par) continue;
Max = max(Max, dp[u.fi]+u.se);
save.push_back(mp(dp[u.fi]+u.se, u.fi));
}
ans = min(ans, mp(Max, v));
save.push_back(mp(reroot[v], 0));
save.push_back(mp(0 , 0));
sort(save.begin(), save.end(), greater<pll>());
for(auto u: T[v])
{
if(u.fi==par) continue;
if(u.fi==save[0].se)
{
reroot[u.fi] = save[1].fi+u.se;
}
else
{
reroot[u.fi] = save[0].fi+u.se;
}
}
//cout << v << " " << reroot[v] << "-\n";
for(auto u: T[v])
{
if(u.fi==par) continue;
dfsk(u.fi, v);
}
}
void solve()
{
cin >> n >> k;
bool dt = 0;
for(int i = 1; i< n; i++)
{
ll a, b, c; cin >> a >> b >> c;
A[i] = val[i] = c;
if(b!=a+1) dt = 1;
T[a].push_back(mp(b,c));
T[b].push_back(mp(a,c));
}
//cout << check(3) << "\n";
if(!dt)
{
solve_large();
return;
}
dfs(1 , 0);
dfsk(1, 0);
cout << ans.fi << "\n" << ans.se;
}
int main()
{
ios_base::sync_with_stdio(NULL) ; cin.tie(nullptr) ; cout.tie(nullptr);
//freopen("B.inp","r",stdin);
ll test_case = 1;
while(test_case--)
{
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
140 ms |
19776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
240 ms |
20372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
