// Time: 06-05-2025 07:34:15
// Problem: A - Commando
// Contest: Virtual Judge - Contest 3
// URL: https://vjudge.net/contest/714915#problem/A
// Memory Limint: 64 MB
// Time Limint: 500 ms
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 1e5 + 1;
int ve[M],dep[M];
ll dp[M];
vector<pair<pair<int,ll>,int>> v,rem[M];
vector<pair<int,int>> nei[M];
pair<ll,int> poi(int m,ll c,int m1,ll c1)
{
return {(c-c1),(m1-m)};
}
bool comp(pair<ll,int> p,pair<ll,int> p1)
{
if (p.first/p.second>p1.first/p1.second)
return 1;
else if(p.first/p.second==p1.first/p1.second)
return 1ll*p.first%p.second*p1.second>1ll*p1.first%p1.second*p.second;
return 0;
}
void add(int m,ll c,int id)
{
while (v.size()>1)
{
pair<int,ll> p={v[v.size()-2].first.first,v[v.size()-2].first.second},p1={v.back().first.first,v.back().first.second};
if (comp(poi(p.first,p.second,m,c),poi(p.first,p.second,p1.first,p1.second)))
rem[id].push_back(v.back()),v.pop_back();
else
break;
}
v.push_back({{m,c},id});
}
ll get(int x)
{
ll ans=1ll*v[0].first.first*x+v[0].first.second;
int s=0,e=v.size();
while (s+1<e)
{
int mid=(s+e)/2;
ll val=1ll*v[mid-1].first.first*x+v[mid-1].first.second;
ll val1=1ll*v[mid].first.first*x+v[mid].first.second;
if (val<val1)
ans=max(ans,val1),s=mid;
else
ans=max(ans,val),e=mid;
}
return ans;
}
void dfs(int u,int p=0)
{
if (!p)
add(0,0,1);
else
{
dp[u]+=-get(-ve[u])+1ll*dep[u]*ve[u];
add(-dep[u],-dp[u],u);
}
while (!nei[u].empty())
{
int i=nei[u].back().first,d=nei[u].back().second;
nei[u].pop_back();
if (i!=p)
dep[i]=dep[u]+d,dfs(i,u);
}
v.pop_back();
reverse(rem[u].begin(),rem[u].end());
for (auto i:rem[u])
add(i.first.first,i.first.second,i.second);
rem[u].clear();
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(NULL), cout.tie(NULL);
int n;
cin>>n;
for (int i=1;i<n;i++)
{
int u,v,d;
cin>>u>>v>>d;
nei[u].push_back({v,d});
nei[v].push_back({u,d});
}
for (int i=2;i<=n;i++)
cin>>dp[i]>>ve[i];
dfs(1);
for (int i=2;i<=n;i++)
cout<<dp[i]<<' ';
cout<<endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |