#include <iostream>
#include <vector>
#include <deque>
using namespace std;
vector<int> edge[100001], wt[100001];
vector<int> order(2, 1), order_index(100001), prev_weight(100001, 0);
vector<int> visit(100001, 0);
vector<long long> S(100001), V(100001);
void dfs(int u)
{
// cerr << "dfs" << u << '\n';
visit[u] = 1;
for(int e = 0; e < edge[u].size(); e++)
{
int v = edge[u][e], w = wt[u][e];
if(visit[v]) continue;
// cerr << "v = " << v << '\n';
order_index[v] = order.size();
order.push_back(v);
// cerr << "pv " << order_index[v] << " = " << w << '\n';
prev_weight[ order_index[v] ] = w;
dfs(v);
}
}
int main()
{
int N;
cin >> N;
for(int i = 1; i <= N-1; i++)
{
long long u, v, d;
cin >> u >> v >> d;
edge[u].push_back(v);
edge[v].push_back(u);
wt[u].push_back(d);
wt[v].push_back(d);
}
order_index[1] = 1;
dfs(1);
// for(int x: order) cerr << x << ' ';
// cerr << '\n';
// for(int k = 0; k <= N+5; k++) cerr << order_index[k] << ' ';
// cerr << '\n';
for(int i = 2; i <= N; i++)
{
int s, v;
cin >> s >> v;
S[ order_index[i] ] = s;
V[ order_index[i] ] = v;
}
long long dist1[N+1];
dist1[1] = 0;
for(int i = 2; i <= N; i++)
dist1[i] = dist1[i-1] + prev_weight[i];
// for(int i = 1; i <= N; i++) cerr << dist1[i] << ' ';
// cerr << '\n';
// for(int i = 1; i <= N; i++) cerr << S[i] << ' ' << V[i] << '\n';
vector<long long> dp(N+1, 0);
/*
p[u] = min{S[u] + V[u]*(dist1[u] - dist1[v]) + dp[v] | v =1..u-1}
= S[u] + V[u]*dist1[u] + min{-dist1[v]*V[u] + dp[v] | v=1..u-1}
line = ax + b = -dist1[v] * V[u] + dp[v]
*/
deque<int> lines;
lines.push_back(1);
for(int i = 2; i <= N; i++)
{
while(lines.size() >= 2)
{
long long a1 = -dist1[lines[0]];
long long b1 = dp[lines[0]];
long long a2 = -dist1[lines[1]];
long long b2 = dp[lines[1]];
if(a2 < a1)
{
swap(a1, a2);
swap(b1, b2);
}
// if(V[u] >= (b1-b2)/(a2-a1))
if(V[i]*(a2-a1) >= b1-b2)
{
// cerr << "popping " << lines.front() << " from front \n";
lines.pop_front();
}
else break;
}
int j = lines[0];
// cerr << "j = " << j << '\n';
dp[i] = S[i] + V[i]*(dist1[i] - dist1[j]) + dp[j];
while(lines.size() >= 2)
{
long long a1 = -dist1[lines[ lines.size()-2 ]];
long long b1 = dp[lines[ lines.size()-2 ]];
long long a2 = -dist1[lines[ lines.size()-1 ]];
long long b2 = dp[lines[ lines.size()-1 ]];
long long a_curr = -dist1[i];
long long b_curr = dp[i];
/*
if((b1-b2)/(a2-a1) >= (b1-b_curr)/(a_curr-a2))
*/
// if(intersect(-2, -1) >= intersect(-1, curr))
if((b1-b2)*(a_curr-a2) >= (b1-b_curr)*(a2-a1))
{
// cerr << "popping " << lines.back() << " from back\n";
lines.pop_back();
}
else break;
}
// cerr << "pushing " << i << " to back\n";
lines.push_back(i);
}
for(int i = 2; i <= N; i++) cout << dp[order_index[i]] << '\n';
}
Compilation message
harbingers.cpp: In function 'void dfs(int)':
harbingers.cpp:15:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for(int e = 0; e < edge[u].size(); e++)
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7704 KB |
Output isn't correct |
| 2 |
Incorrect |
9 ms |
8012 KB |
Output isn't correct |
| 3 |
Incorrect |
120 ms |
13920 KB |
Output isn't correct |
| 4 |
Incorrect |
159 ms |
16860 KB |
Output isn't correct |
| 5 |
Incorrect |
208 ms |
19776 KB |
Output isn't correct |
| 6 |
Incorrect |
275 ms |
22432 KB |
Output isn't correct |
| 7 |
Incorrect |
155 ms |
15548 KB |
Output isn't correct |
| 8 |
Incorrect |
243 ms |
19332 KB |
Output isn't correct |
| 9 |
Incorrect |
300 ms |
20856 KB |
Output isn't correct |
| 10 |
Incorrect |
230 ms |
19864 KB |
Output isn't correct |
