#include <bits/stdc++.h>
using namespace std;
struct line {
long long a,b;
double intersectX(line l) {return (b-l.b)/(l.a-a);}
};
const int N = 1e5+1;
stack<pair<int,int>> ch;
vector<int> id(N);
deque<int> slop;
line l[N];
long long dp[N];
vector<pair<int,int>> adj[N];
int A[N];
int B[N];
void rollback(int i) {
while (ch.top().first != i || ch.top().second != 1) {
auto op = ch.top();
ch.pop();
if (op.second == 1) {
slop.pop_back();
} else {
slop.push_back(op.first);
}
}
}
double intersect(int i, int j) {
if (l[i].a > l[j].a) swap(i,j);
return (l[i].b-l[j].b)/(l[j].a-l[i].a);
}
bool cmp(int idx, int a) {
return intersect(slop[idx],slop[idx+1]) < a;
}
void insert(int idx) {
while (slop.size() > 1 && intersect(slop[slop.size()-2],slop.back()) >= intersect(slop.back(),idx)) {
ch.push({slop.back(),-1});
slop.pop_back();
}
ch.push({idx,1});
slop.push_back(idx);
}
void dfs(int i, int p,int curr) {
if (i != 0) {
int j = slop[*lower_bound(id.begin(),id.begin()+slop.size()-1,A[i],cmp)];
dp[i] = curr*A[i] + B[i] -(l[j].a*A[i] + l[j].b);
}
l[i].a = curr;
l[i].b = -dp[i];
insert(i);
for(pair<int,int> u : adj[i]) {
if (u.first != p) {
dfs(u.first,i,curr+u.second);
rollback(i);
}
}
}
int main() {
iota(id.begin(),id.end(),0);
int n; cin >> n;
int a,b,c;
dp[0]=0;
for(int i = 1; i < n; i++) {
cin >> a >> b >>c;
--a; --b;
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
for(int i = 1; i< n; i++) {
cin >> B[i] >> A[i];
}
dfs(0,-1,0);
for(int i = 1; i < n; i++) {
cout << dp[i] << endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
3024 KB |
Output is correct |
2 |
Correct |
8 ms |
3560 KB |
Output is correct |
3 |
Incorrect |
115 ms |
12044 KB |
Output isn't correct |
4 |
Incorrect |
181 ms |
16184 KB |
Output isn't correct |
5 |
Incorrect |
225 ms |
20552 KB |
Output isn't correct |
6 |
Correct |
298 ms |
23564 KB |
Output is correct |
7 |
Incorrect |
193 ms |
13364 KB |
Output isn't correct |
8 |
Incorrect |
277 ms |
18224 KB |
Output isn't correct |
9 |
Incorrect |
303 ms |
20308 KB |
Output isn't correct |
10 |
Incorrect |
253 ms |
18840 KB |
Output isn't correct |