#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1e5+5;
mt19937 rng(12345678);
ll n, dp[nx][2], sm[nx], tot;
vector<pair<ll, ll>> d[nx];
struct treap
{
struct node
{
ll sm, vl, key, sz;
node *l, *r;
node(ll vl): sm(vl), vl(vl), key(rng()), sz(1), l(0), r(0){}
};
typedef node* pnode;
pnode rt;
ll getsz(pnode x) {return x?x->sz:0;}
ll getsm(pnode x) {return x?x->sm:0;}
void update(pnode x)
{
if (!x) return;
x->sz=1+getsz(x->l)+getsz(x->r);
x->sm=x->vl+getsm(x->l)+getsm(x->r);
}
void merge(pnode l, pnode r, pnode &k)
{
if (!l||!r) return k=l?l:r, void();
if (l->key>=r->key) merge(l->r, r, l->r), k=l;
else merge(l, r->l, r->l), k=r;
update(k);
}
void split(pnode &l, pnode &r, pnode k, int key)
{
if (!k) return l=r=0, void();
if (1+getsz(k->r)<=key) split(l, k->l, k->l, key-(1+getsz(k->r))), r=k;
else split(k->r, r, k->r, key), l=k;
update(l), update(r);
}
void splitlowerbound(pnode &l, pnode &r, pnode k, ll vl)
{
if (!k) return l=r=0, void();
if (k->vl>=vl) splitlowerbound(l, k->l, k->l, vl), r=k;
else splitlowerbound(k->r, r, k->r, vl), l=k;
update(l), update(r);
}
void insert(ll vl)
{
pnode p1, p2, p3=new node(vl);
splitlowerbound(p1, p2, rt, vl);
merge(p1, p3, rt);
merge(rt, p2, rt);
}
ll query(ll k)
{
pnode p1, p2;
split(p1, p2, rt, k);
auto tmp=getsm(p2);
merge(p1, p2, rt);
return tmp;
}
void show(pnode x)
{
if (!x) return;
show(x->l);
cout<<x->vl<<' ';
show(x->r);
}
} t[nx];
void dfs(int u, int p, ll pw, int k)
{
//cout<<"dfs "<<u<<' '<<p<<' '<<pw<<' '<<k<<'\n';
sm[u]=0;
t[u].rt=0;
for (auto [v, w]:d[u]) if (v!=p) dfs(v, u, w, k), sm[u]+=dp[v][0], t[u].insert(dp[v][1]-dp[v][0]);
dp[u][0]=sm[u]+t[u].query(k);
dp[u][1]=sm[u]+t[u].query(k-1)+pw;
dp[u][1]=max(dp[u][1], dp[u][0]);
//if (k==2) cout<<"dp "<<u<<' '<<dp[u][0]<<' '<<dp[u][1]<<'\n';
//if (k==2&&u==0) cout<<"treap : ", t[u].show(t[u].rt), cout<<'\n';
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
n=N;
vector<ll> mx(n);
for (int i=0; i<n-1; i++) d[U[i]].push_back({V[i], W[i]}), d[V[i]].push_back({U[i], W[i]}), tot+=W[i];
// minimum closure costs = total - maximum selected road
for (int i=1; i<n; i++) dfs(0, 0, 0, i), mx[i]=dp[0][0];
for (int i=0; i<n; i++) mx[i]=tot-mx[i];
return mx;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |