#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long INF = 1'000'000'000'000'000'000LL;
const int maxN = 100000;
int N;
vector<int> edge[maxN+1];
vector<long long> wt[maxN+1];
long long S[maxN+1], V[maxN+1];
vector<int> parent(maxN+1, -1);
vector<long long> dist1(maxN+1);
vector< vector<int> > cht_anc(maxN+1, vector<int>(20));
vector<long long> dp(maxN+1, INF);
/*
dp[u] = min{S[u] + V[u]*(dist1[u] - dist1[v]) + dp[v] | v in ancs[u]}
= S[u] + V[u]*dist1[u] + min{-dist1[v]*V[u] + dp[v] | v in ancs[u]}
line = ax + b = -dist1[v] * V[u] + dp[v]
*/
bool cmp_Xgeq(long long X, int l1, int l2) // return X >= intersect(l1, l2)
{
if(l1 == 0 || l2 == 0) return 1;
long long a1 = -dist1[l1];
long long b1 = dp[l1];
long long a2 = -dist1[l2];
long long b2 = dp[l2];
//guarantee a1 >= a2
if(a1 < a2)
{
swap(a1, a2);
swap(b1, b2);
}
/*intersect((a1, b1), (a2, b2)) = I
a1*I + b1 = a2*I + b2
(a1-a2)I = b2-b1
I = (b2-b1)/(a1-a2)
*/
return ( (a1-a2)*X >= b2-b1 );
}
bool cmp_lines(int l1, int l2, int L1, int L2)
{
if(l1 == 0 || l2 == 0) return 0;
if(L1 == 0 || L2 == 0) return 1;
long long a1 = -dist1[l1];
long long b1 = dp[l1];
long long a2 = -dist1[l2];
long long b2 = dp[l2];
//guarantee a1 >= a2
if(a1 < a2)
{
swap(a1, a2);
swap(b1, b2);
}
long long A1 = -dist1[L1];
long long B1 = dp[L1];
long long A2 = -dist1[L2];
long long B2 = dp[L2];
//guarantee A1 >= A2
if(A1 < A2)
{
swap(A1, A2);
swap(B1, B2);
}
//return (b2-b1)/(a1-a2) <= (B2-B1)/(A1-A2)
return (b2-b1)*(A1-A2) < (B2-B1)*(a1-a2);
}
void dfs(int u)
{
// cerr << "\n\n\n\n\n\n\n\n";
// cerr << "!!! DFS " << u << " !!! \n";
if(u != 1)
{
/*
PART 1: Locate the optimal line to compute dp[u] from.
We locate a CHT ancestor of u: v which is the optimal line.
We want the highest possible v such that V[u] >= intersect(v, p[v])
*/
int v = parent[u];
// cerr << v << ' ' << cht_anc[v][0] << ' ' << cht_anc[v][1] << '\n';
// for(int bit = 19; bit >= 0; bit--)
// {
// if(cht_anc[v][bit] == 0) continue;
// // cerr << "bit = " << bit << '\n';
//
// int temp = cht_anc[v][bit];
//
// // cerr << "temp = " << temp << '\n';
//
// if(cmp_Xgeq(V[u], temp, cht_anc[temp][0]))
// {
// v = temp;
// // cerr << "jumped! \n";
// }
// }
int v1 = parent[u];
for(int bit = 19; bit >= 0; bit--)
{
// if(cht_anc[v1][bit] == 0) continue;
int temp = cht_anc[v1][bit];
if(temp == 0 || cht_anc[temp][0] == 0) continue;
if(!cmp_Xgeq(V[u], temp, cht_anc[temp][0]))
{
v1 = temp;
}
}
if(!cmp_Xgeq(V[u], v1, cht_anc[v1][0]))
v = parent[v1];
else
v = v1;
// cerr << "computation v = " << v << '\n';
dp[u] = S[u] + V[u]*(dist1[u] - dist1[v]) + dp[v];
// cerr << "ideal evaluator line for " << u << " = " << v << '\n';
// cerr << "for line " << u << ", a = " << -dist1[u] << " and b = " << dp[u] << '\n';
//
// cerr << "\n\n";
/*
PART 2: Find the appropriate CHT parent of u.
Find the first ancestor a such that intersect(p[a], a) < intersect(a, u)
Find the last ancestor v such that intersect(p[v], v) >= intersect(v, u);
*/
cht_anc[u][0] = parent[u];
v = u;
for(int bit = 19; bit >= 0; bit--)
{
int temp = cht_anc[v][bit];
if(temp == 0 || cht_anc[temp][0] == 0) continue;
if(cmp_lines(temp, u, temp, cht_anc[temp][0]))
{
v = temp;
}
// cerr << "bit = " << bit << ", v = " << temp << '\n';
}
int a = cht_anc[v][0];
// cerr << "cht parent of " << u << " = " << a << '\n';
cht_anc[u][0] = a;
for(int bit = 1; bit < 20; bit++)
cht_anc[u][bit] = cht_anc[ cht_anc[u][bit-1] ][bit-1];
}
for(int e = 0; e < edge[u].size(); e++)
{
int v = edge[u][e];
long long d = wt[u][e];
if(parent[v] != -1) continue;
parent[v] = u;
dist1[v] = dist1[u] + d;
dfs(v);
}
}
int main()
{
cin >> N;
for(int e = 1; e <= N-1; e++)
{
int u, v;
long long d;
cin >> u >> v >> d;
edge[u].push_back(v);
wt[u].push_back(d);
edge[v].push_back(u);
wt[v].push_back(d);
}
for(int i = 2; i <= N; i++) cin >> S[i] >> V[i];
parent[1] = 0;
dist1[1] = 0;
dp[1] = 0;
S[1] = V[1] = 0;
for(int x = 0; x < 20; x++)
cht_anc[1][x] = 0;
// cerr << "check\n";
dfs(1);
for(int i = 2; i <= N; i++) cout << dp[i] << '\n';
}
Compilation message
harbingers.cpp: In function 'void dfs(int)':
harbingers.cpp:210:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
210 | for(int e = 0; e < edge[u].size(); e++)
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
18716 KB |
Output isn't correct |
| 2 |
Incorrect |
22 ms |
19148 KB |
Output isn't correct |
| 3 |
Incorrect |
147 ms |
27516 KB |
Output isn't correct |
| 4 |
Incorrect |
230 ms |
31388 KB |
Output isn't correct |
| 5 |
Runtime error |
346 ms |
35716 KB |
Memory limit exceeded |
| 6 |
Runtime error |
453 ms |
39312 KB |
Memory limit exceeded |
| 7 |
Incorrect |
239 ms |
29316 KB |
Output isn't correct |
| 8 |
Runtime error |
407 ms |
34336 KB |
Memory limit exceeded |
| 9 |
Runtime error |
470 ms |
36292 KB |
Memory limit exceeded |
| 10 |
Runtime error |
415 ms |
35032 KB |
Memory limit exceeded |
