Submission #548491

#TimeUsernameProblemLanguageResultExecution timeMemory
548491kymPaths (RMI21_paths)C++14
100 / 100
345 ms26600 KiB
#include <bits/stdc++.h> using namespace std; #define int ll #define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i) #define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i) #define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL #define db(x) cerr << #x << "=" << x << "\n" #define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n" #define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n" #define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n" #define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{" << ite.f << ',' << ite.s << "} "; cerr << "\n" #define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n" #define reach cerr << "LINE: " << __LINE__ << "\n"; #else #define db(x) #define db2(x,y) #define db3(a,b,c) #define dbv(v) #define dbvp(v) #define dba(a,ss,ee) #define reach #endif mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define ll long long #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define f first #define s second #define g0(x) get<0>(x) #define g1(x) get<1>(x) #define g2(x) get<2>(x) #define g3(x) get<3>(x) typedef pair <ll, ll> pi; typedef tuple<ll,ll,ll> ti3; typedef tuple<ll,ll,ll,ll> ti4; ll rand(ll a, ll b) { return a + rng() % (b-a+1); } const int MOD = 1e9 + 7; const int inf = (int)1e9 + 500; const long long oo = (ll)1e18 + 500; template <typename T> void chmax(T& a, const T b) { a=max(a,b); } template <typename T> void chmin(T& a, const T b) { a=min(a,b); } const int MAXN = 100005; int n,k; vector<pi> V[MAXN]; set<pi> in; // {num[x],x} set<pi,greater<pi>> out; // {num[x], x} int dist[MAXN]; pi down[MAXN]; pi up[MAXN]; int par[MAXN]; int num[MAXN]; int W[MAXN]; int output[MAXN]; int st[MAXN]; int en[MAXN]; int cnt; vector<int> leaves; bool ispar(int p, int x) { if(st[p] <= st[x] && en[p] >= en[x]) return 1; else return 0; } pi dfs1(int x, int p) { st[x]=cnt++; par[x] = p; if(V[x].size() == 1 && p != -1) { leaves.pb(x); down[x]=pi(0, x); en[x]=cnt-1; return pi(0,x); } for(auto v:V[x])if(v.f != p){ dist[v.f] = dist[x] + v.s; W[v.f] = v.s; pi r=dfs1(v.f,x); r.f += v.s; chmax(down[x],r); } en[x]=cnt-1; return down[x]; } void dfs2(int x, int p) { vector<pi> vec; vec.pb(pi(up[x].f+W[x], up[x].s)); for(auto v:V[x])if(v.f != p) { vec.pb(pi(down[v.f].f+v.s, down[v.f].s)); sort(all(vec), [](pi a, pi b) { return a.f > b.f; }); while((int)vec.size() >= 3)vec.pop_back(); } for(auto v:V[x])if(v.f != p){ if(ispar(v.f,vec[0].s)) { up[v.f]=vec[1]; } else { up[v.f]=vec[0]; } } for(auto v:V[x])if(v.f != p) dfs2(v.f,x); } int ans; void update(int x, int nval) { if(in.size() && in.find(pi(num[x],x)) != in.end()) { auto it=in.find(pi(num[x],x)); pi into = pi(it->f+nval,it->s); in.erase(it); in.insert(pi(into.f,into.s)); num[x]+=nval; ans += nval; } else if(out.size() && out.find(pi(num[x],x)) != out.end()) { auto it=out.find(pi(num[x],x)); pi into = pi(it->f+nval,it->s); out.erase(it); out.insert(pi(into.f,into.s)); num[x]+=nval; } else{ assert(in.empty() || out.empty()); } } void rebalance() { if(in.empty() || out.empty()) return; pi inside=*in.begin(); pi outside=*out.begin(); while(inside.f < outside.f) { ans += outside.f; ans -= inside.f; in.erase(in.begin()); out.erase(out.begin()); in.insert(outside); out.insert(inside); inside=*in.begin(); outside=*out.begin(); } } void solve(int x, int p) { output[x] = ans; db(x); for(auto v:V[x])if(v.f!=p) { pi r1 = down[v.f]; pi r2 = up[v.f]; update(r1.s, -W[v.f]); update(r2.s, W[v.f]); rebalance(); solve(v.f, x); update(r1.s, W[v.f]); update(r2.s, -W[v.f]); rebalance(); db(x); dbvp(in); dbvp(out); } } int32_t main() { IAMSPEED cin >> n >> k; FOR(i,1,n-1) { int a,b,c; cin >> a >> b >> c; V[a].pb(pi(b,c)); V[b].pb(pi(a,c)); } dfs1(1,-1); reach up[1] = pi(0,1); dfs2(1,-1); FOR(i,2,n) { db3(i,down[i].s,down[i].f); db3(i,up[i].s,up[i].f); num[down[i].s]+=W[i]; } for(auto i:leaves) { out.insert(pi(num[i],i)); } if(V[1].size() == 1)out.insert(pi(0,1)); dbv(leaves); while(out.size() && (int)in.size() < k) { in.insert(*out.begin()); ans += out.begin()->f; out.erase(out.begin()); } if((int)in.size() < k) { //just take every single edge. FOR(i,1,n) { cout << ans << '\n'; } exit(0); } reach solve(1,-1); FOR(i,1,n) cout << output[i] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...