#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define pb push_back
#define ss second
#define ff first
#define all(x) (x).begin(), (x).end()
const int nax = 1e5 + 4;
int n, k, sz = 1;
vector<pii> adj[nax];
vector<pll> st;
vector<ll> lazy;
ll d[nax], rep[nax];
int dpar[nax];
int par[nax], vis[nax], eul[nax], endeul[nax], cor[nax];
int cureul = -1;
void dfs(int x, ll curd, int p)
{
par[x] = p;
d[x] = curd;
dpar[x] = curd - d[p];
vis[x] = 0;
eul[x] = ++cureul;
cor[cureul] = x;
for(auto e: adj[x])
{
if(e.ff == p)
continue;
dfs(e.ff, curd + (ll)(e.ss), x);
}
endeul[x] = cureul;
}
void build(int p, int l, int r)
{
if(l == r)
{
st[p] = {d[cor[l]], cor[l]};
lazy[p] = 0ll;
return ;
}
build(2 * p, l, (l + r)/2);
build(2 * p + 1, (l + r)/2 + 1, r);
st[p] = max(st[2 * p], st[2 * p + 1]);
lazy[p] = 0ll;
}
void propagate(int p, int l, int r)
{
if(lazy[p])
{
if(l != r)
{
lazy[2 * p] += lazy[p];
lazy[2 * p + 1] += lazy[p];
}
st[p].ff += lazy[p];
lazy[p] = 0ll;
}
}
void update(int p, int l, int r, int i, int j, ll val)
{
propagate(p, l, r);
if(i > j)
return ;
if(l >= i && r <= j)
{
lazy[p] += val;
propagate(p, l, r);
return ;
}
int m = (l + r)/2;
update(2 * p, l, m, i, min(j, m), val);
update(2 * p + 1, m + 1, r, max(i, m + 1), j, val);
pll a ={st[2 * p].ff + lazy[2 * p], st[2 * p].ss} ;
pll b ={st[2 * p + 1].ff + lazy[2 * p + 1], st[2 * p + 1].ss};
st[p] = max(a,b);
return ;
}
pll query(int p, int l, int r, int i, int j)
{
propagate(p, l, r);
if(i > j)
return {0ll, 0ll};
if(l >= i && r <= j)
return st[p];
int m = (l + r)/2;
return max(query(2 * p, l, m, i, min(j, m)),
query(2 * p + 1, m + 1, r, max(i, m + 1), j));
}
void dfs2(int x, int p, ll v)
{
update(1, 0, sz - 1, eul[x], endeul[x], -v);
update(1, 0, sz - 1, 0, eul[x] - 1, v);
update(1, 0, sz - 1, endeul[x] + 1, n - 1, v);
rep[x] = query(1, 0 , k - 1, 0, n - 1);
for(auto e: adj[x])
{
if(e.ff == p)
continue;
dfs2(e.ff, x, e.ss);
}
update(1, 0, sz - 1, eul[x], endeul[x], v);
update(1, 0, sz - 1, 0, eul[x] - 1, -v);
update(1, 0, sz - 1, endeul[x] + 1, n - 1, -v);
}
void solve()
{
cin >> n >> k;
for(int i= 1; i < n; i++)
{
int a, b;
cin >> a >> b;
ll c; cin >> c;
adj[a].pb({b, c});
adj[b].pb({a, c});
}
dfs(1, 0, 0);
while(sz < n)
sz = (sz << 1);
lazy.assign(2 * sz + 1, 0);
st.assign(2 * sz + 1, {0, 0});
build(1, 0, sz - 1);
dfs2(1, 0, 0);
for(int root = 1; root <= n; root++)
{
if(k > 1)
{
cureul = -1;
dfs(root, 0, 0);
build(1, 0, sz - 1);
vis[root] = 1;
ll ans = 0ll;
for(int i = 1;i <= k; i++)
{
propagate(1, 0, sz - 1);
pll o = st[1];
if(o.ff == 0)
break;
int cur = o.ss;
ans += o.ff;
while(!vis[cur])
{
update(1, 0, sz - 1, eul[cur], endeul[cur], -dpar[cur]);
vis[cur] = 1;
cur= par[cur];
}
}
cout << ans << '\n';
}
else
{
cout << rep[root] << '\n';
}
}
}
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tt = 1;
while(tt--)
solve();
}
Compilation message
Main.cpp: In function 'void dfs2(int, int, ll)':
Main.cpp:102:19: error: cannot convert 'pll' {aka 'std::pair<long long int, long long int>'} to 'll' {aka 'long long int'} in assignment
102 | rep[x] = query(1, 0 , k - 1, 0, n - 1);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| |
| pll {aka std::pair<long long int, long long int>}
