| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1278391 | Ice_man | Harbingers (CEOI09_harbingers) | C++20 | 0 ms | 0 KiB |
/**
____ ____ ____ __________________ ____ ____ ____
||I || ||c || ||e || || || ||M || ||a || ||n ||
||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__||
|/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\|
*/
#include <iostream>
#include <chrono>
#include <vector>
#define maxn 200005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define PB push_back
#define X first
#define Y second
#define control cout<<"passed"<<endl;
typedef unsigned long long ull;
typedef long long ll;
typedef __int128 lint;
typedef std::pair <ll, ll> pll;
typedef std::pair <ll, ll> pil;
typedef std::pair <ll, ll> pli;
typedef long double ld;
struct CHT
{
std::vector <pll> hull;
lint calc(pll curr, ll x)
{
return (lint)(curr.X) * x + curr.Y;
}
long double llersection(pll a, pll b)
{
return (litn)(b.Y - a.Y) / (a.X - b.X);
}
bool check(pll l1 , pll l2 , pll l3)
{
return __int128(l2.b - l1.b) * (l2.m - l3.m) >= __int128(l3.b - l2.b) * (l1.m - l2.m);
}
void add_line(pll curr)
{
while(hull.size() >= 2)
{
if(bad(hull[hull.size() - 2] , hull.back() , curr) == true)
hull.pop_back();
else
break;
}
hull.PB(curr);
}
ll query(double x)
{
if(hull.size() == 0)
return 4e18;
ll l = 0, r = hull.size() - 1;
while(l < r)
{
ll mid = (l + r) / 2;
if(calc(hull[mid], x) > calc(hull[mid + 1], x))
l = mid + 1;
else
r = mid;
}
return calc(hull[l], x);
}
};
std::vector <pll> v[maxn];
ll depth[maxn], sz[maxn], up[maxn], lead[maxn];
std::vector <ll> d[maxn];
ll dist[maxn];
void dfs_sz(ll node, ll par)
{
d[depth[node]].PB(node);
up[node] = par;
sz[node] = 1;
for(auto& nb : v[node])
{
if(nb.X == par)
continue;
depth[nb.X] = depth[node] + 1;
dist[nb.X] = dist[node] + nb.Y;
dfs_sz(nb.X, node);
sz[node] += sz[nb.X];
}
}
ll heavy[maxn];
ll cnt = 0;
void dfs_hld(ll node, ll par, ll le)
{
//std::cout << node << " " << par << " " << le << "\n";
lead[node] = le;
heavy[node] = -1;
for(auto& nb : v[node])
{
if(nb.X == par)
continue;
if(heavy[node] == -1 || (sz[nb.X] > sz[heavy[node]] && nb.X != par))
heavy[node] = nb.X;
}
//std::cout << "!! " << heavy[node] << "\n";
if(heavy[node] == -1)
return;
dfs_hld(heavy[node], node, le);
for(auto& nb : v[node])
if(nb.X != par && nb.X != heavy[node])
dfs_hld(nb.X, node, nb.X);
}
CHT h[maxn];
ll speed[maxn], wait[maxn];
ll answer(ll node)
{
//std::cout << "------------------------------" << "\n";
//std::cout << node << "\n";
ll ans = 4e18;
ll start = node;
while(node != 0)
{
/**std::cout << node << "\n";
std::cout << h[lead[node]].query(speed[start]) << "\n";
std::cout << "!!!!!" << "\n" << speed[node] << ": ";
for(auto& e : h[lead[node]].hull)
std::cout << "{ " << e.X << " " << e.Y << " } ";
std::cout << "\n";
std::cout << "!!!!!" << "\n";*/
ans = std::min(ans, h[lead[node]].query(-speed[start]));
node = up[lead[node]];
}
return ans;
}
ll n;
ll dp[maxn];
void read()
{
std::cin >> n;
for(ll i = 1; i <= n - 1; i++)
{
ll x, y, z;
std::cin >> x >> y >> z;
v[x].PB({y, z});
v[y].PB({x, z});
}
for(ll i = 1; i <= n - 1; i++)
std::cin >> wait[i + 1] >> speed[i + 1];
dist[1] = 0;
up[1] = 0;
depth[1] = 0;
dfs_sz(1, 0);
//std::cout << "here" << "\n";
dfs_hld(1, 0, 1);
//std::cout << "here" << "\n";
dp[1] = 0;
for(ll i = 1; i <= n - 1; i++)
{
//std::cout << "****************************" << "\n";
for(auto& node : d[i])
{
dp[node] = wait[node] + speed[node] * dist[node];
//std::cout << "?------? " << node << " " << answer(node) << " " << dist[node] * speed[node] + wait[node] << "\n";
ll pom = answer(node);
if(pom == 4e18)
continue;
dp[node] = std::min(dp[node], pom + dist[node] * speed[node] + wait[node]);
}
for(auto& node : d[i])
h[lead[node]].add_line({dist[node], dp[node]});
}
for(ll i = 2; i <= n; i++)
std::cout << dp[i] << " ";
std::cout << "\n";
}
int main()
{
/**#ifdef ONLINE_JUDGE /// promeni
freopen("taxi.in", "r", stdin);
freopen("taxi.out", "w", stdout);
#endif*/
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
read();
return 0;
}