#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MN = 1e5+5;
int N, sz[MN]; vector<pair<int,int>> adjl[MN]; ll ans[MN]; vector<ll> diffs[MN];
template <class T> void clr(T pq[]){
while(!pq[1].empty() && pq[1].top() == pq[0].top()){
pq[1].pop();
pq[0].pop();
}
}
struct KMin{
priority_queue<ll> iq[2]; priority_queue<ll, vector<ll>, greater<ll>> oq[2];
int k, infs, sz; ll curSum;
void init(int _k){
iq[0] = iq[1] = {};
oq[0] = oq[1] = {};
k = _k;
sz = infs = 0;
curSum = 0;
}
void insert(ll x){
curSum += x;
iq[0].push(x);
if(++sz > k){
clr(iq);
ll rem = iq[0].top(); iq[0].pop();
oq[0].push(rem);
curSum -= rem;
}
}
void erase(ll x){
assert(sz--);
if(clr(iq); iq[0].top() >= x){
curSum -= x;
iq[1].push(x);
if(sz >= k){
clr(oq);
ll ins = oq[0].top(); oq[0].pop();
iq[0].push(ins);
curSum += ins;
}
} else oq[1].push(x);
}
void decK(){ insert(0); }
ll query(){ return curSum; }
} kMin;
void dfs(int u, int pw){
sort(adjl[u].begin(), adjl[u].end(), [](pair<int,int> lhs, pair<int,int> rhs){
return sz[lhs.first] > sz[rhs.first];
});
for(auto [v, w]: adjl[u]){
adjl[v].erase(find(adjl[v].begin(), adjl[v].end(), pair(u, w)));
dfs(v, w);
}
diffs[u].resize(sz[u]);
kMin.init(sz[u] - 1);
for(auto [v, w]: adjl[u])
kMin.insert(w);
for(int k = 1; k < sz[u]; k++){
for(auto [v, w]: adjl[u]){
if(sz[v] <= k) break;
kMin.erase(w);
kMin.insert(w - diffs[v][k]);
assert(w >= diffs[v][k]);
}
assert(kMin.k == sz[u] - k);
ll res1 = kMin.query();
kMin.decK();
ll res2 = kMin.query();
ans[k] += res1;
diffs[u][k] = res1 - res2;
ans[k] += min(0LL, pw - diffs[u][k]);
diffs[u][k] = min(ll(pw), diffs[u][k]);
for(auto [v, w]: adjl[u]){
if(sz[v] <= k) break;
kMin.insert(w);
kMin.erase(w - diffs[v][k]);
}
}
}
vector<ll> minimum_closure_costs(int _N, vector<int> us, vector<int> vs,
vector<int> ws){
N = _N;
for(int i = 0, u, v, w; i < N-1; i++){
u = us[i]; v = vs[i]; w = ws[i];
adjl[u].emplace_back(v, w);
adjl[v].emplace_back(u, w);
}
for(int i = 0; i < N; i++)
sz[i] = adjl[i].size();
++sz[0];
dfs(0, 0);
ans[0] = accumulate(ws.begin(), ws.end(), 0LL);
for(int k = 1; k < sz[0]; k++)
ans[k] -= diffs[0][k];
return vector<ll>(ans, ans+N);
}
#ifdef LOCAL_PROJECT
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int N; cin >> N;
vector<int> us(N-1), vs(N-1), ws(N-1);
for(int i = 0; i < N-1; i++)
cin >> us[i] >> vs[i] >> ws[i];
vector<ll> ans = minimum_closure_costs(N, us, vs, ws);
for(int i = 0; i < N; i++)
printf("%d%c", ans[i], " \n"[i==N-1]);
return 0;
}
#endif
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Runtime error |
9 ms |
10452 KB |
Execution killed with signal 6 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
74 ms |
28632 KB |
Output is correct |
3 |
Correct |
83 ms |
31696 KB |
Output is correct |
4 |
Correct |
80 ms |
33484 KB |
Output is correct |
5 |
Correct |
81 ms |
33484 KB |
Output is correct |
6 |
Correct |
5 ms |
5380 KB |
Output is correct |
7 |
Correct |
5 ms |
5460 KB |
Output is correct |
8 |
Correct |
4 ms |
5588 KB |
Output is correct |
9 |
Correct |
4 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
62 ms |
22144 KB |
Output is correct |
13 |
Correct |
79 ms |
33452 KB |
Output is correct |
14 |
Correct |
2 ms |
4948 KB |
Output is correct |
15 |
Correct |
67 ms |
30700 KB |
Output is correct |
16 |
Correct |
76 ms |
33580 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Runtime error |
7 ms |
9948 KB |
Execution killed with signal 6 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Runtime error |
7 ms |
9948 KB |
Execution killed with signal 6 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
51 ms |
22544 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
51 ms |
22544 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Runtime error |
9 ms |
10452 KB |
Execution killed with signal 6 |
3 |
Halted |
0 ms |
0 KB |
- |