#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(x) begin(x), end(x)
#define pb push_back
#define int long long
const int inf = 1e18;
struct line{
int m, c;
double p;
int eval(int x){
return m*x+c;
}
};
struct CHT{
vector<line> hull; int id;
CHT() { id = 0;}
double getx(int m1, int c1, int m2, int c2){
if(m1==m2) return inf;
else return (double)(c1-c2)/(double)(m2-m1);
}
void addline(int m, int c){
double p = -inf;
while(!hull.empty()){
line last = hull.back();
p = getx(m, c, last.m, last.c);
if(p==inf){
if(c>last.c) return;
else hull.pop_back();
}
else if(p<last.p) hull.pop_back();
else break;
}
hull.pb((line){m, c, p});
}
int best(int x){
int k = 0;
int L = 0, R = hull.size()-1;
while(L<=R){
int mid = (L+R)/2;
if(hull[mid].p <= x){
k = mid; L = mid+1;
}
else R = mid-1;
}
return hull[k].eval(x);
}
int fast(int x){
while(id+1<(int)hull.size() and hull[id+1].p <= x) id++;
return hull[id].eval(x);
}
};
vector<pii> adj[100001];
int dist[100001], dp[100001];
CHT cht[100001];
int S[100001], F[100001];
void dfs(int s, int e){
for(auto pr: adj[s]){
int u = pr.first;
if(u == e) continue;
dist[u] = dist[s] + pr.second;
CHT temp = cht[s];
dp[u] = temp.best(F[u]) + S[u] + F[u]*dist[u];
temp.addline(-dist[u], dp[u]);
cht[u] = temp;
dfs(u, s);
}
cht[s].hull.clear();
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N; cin >> N;
for(int i=0; i<N-1; i++){
int a, b, d; cin >> a >> b >> d;
adj[a].pb({b, d}); adj[b].pb({a, d});
}
for(int i=2; i<=N; i++){
cin >> S[i] >> F[i];
}
dist[1] = 0; dp[1] = 0;
cht[1].addline(0, 0);
dfs(1, 0);
for(int i=2; i<=N; i++) cout << dp[i] << ' ';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
8792 KB |
Output is correct |
2 |
Correct |
4 ms |
10596 KB |
Output is correct |
3 |
Runtime error |
43 ms |
65536 KB |
Execution killed with signal 9 |
4 |
Runtime error |
46 ms |
65536 KB |
Execution killed with signal 9 |
5 |
Runtime error |
75 ms |
65536 KB |
Execution killed with signal 9 |
6 |
Runtime error |
110 ms |
65536 KB |
Execution killed with signal 9 |
7 |
Runtime error |
76 ms |
41108 KB |
Memory limit exceeded |
8 |
Runtime error |
63 ms |
65536 KB |
Execution killed with signal 9 |
9 |
Runtime error |
59 ms |
65536 KB |
Execution killed with signal 9 |
10 |
Runtime error |
58 ms |
65536 KB |
Execution killed with signal 9 |