This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,long long>> adj[2001];
int in[2001],outt[2001];
pair<long long,long long>P[2001];int decode[2001];int timer = 0;
pair<long long,long long> seg[8001];long long lazy[8001];
void build(int p,int l,int r){
lazy[p] = 0;
if(l==r){
seg[p].second = decode[l];
seg[p].first = 0;
return;
}
int md = (l+r)/2;
build(p*2,l,md);
build(p*2+1,md+1,r);
seg[p] = max(seg[p*2],seg[p*2+1]);
}
void prop(int p,int l,int r){
seg[p].first+=lazy[p];
if(l!=r){
lazy[p*2]+=lazy[p];
lazy[p*2+1]+=lazy[p];
}
lazy[p] = 0;
}
void update(int p,int l,int r,int lq,int rq,long long val){
prop(p,l,r);
if(l>=lq&&r<=rq){
lazy[p]+=val;
prop(p,l,r);
return ;
}
if(r<lq||l>rq)return ;
int md = (l+r)/2;
update(p*2,l,md,lq,rq,val);
update(p*2+1,md+1,r,lq,rq,val);
seg[p] = max(seg[p*2],seg[p*2+1]);
}
void dfs(int i,int pr){
in[i] = ++timer;
decode[timer] = i;
for(auto j:adj[i]){
if(j.first==pr)continue;
dfs(j.first,i);
}
outt[i] = timer;
}
int n;
void go(int i,int pr,long long la){
P[i] = {pr,la};
for(auto j:adj[i]){
if(j.first==pr)continue;
update(1,1,n,in[j.first],outt[j.first],j.second);
go(j.first,i,j.second);
}
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int k;
cin>>n>>k;
for(int i = 0;i<n-1;i++){
int a,b,c;cin>>a>>b>>c;
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
for(int r = 1;r<=n;r++){
timer = 0;
dfs(r,0);
build(1,1,n);
go(r,0,0);
int e = k;
long long all = 0;
while(e--){
int no = seg[1].second;
while(no!=r){
if(P[no].second==0){
break;
}
update(1,1,n,in[no],outt[no],-P[no].second);
all+=P[no].second;
P[no].second = 0;
no = P[no].first;
}
}
cout<<all<<endl;
}
}
# | 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... |