#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<complex>
#include<cassert>
#include<stack>
using namespace std;
typedef long long ll;
typedef complex<double> pt;
typedef pair<ll, ll> pii;
#define x() real()
#define y() imag()
#define smx(a, b) a = max(a, b)
#define smn(a, b) a = min(a, b)
#define in(mp, v) (mp.find(v) != mp.end())
const int MAXN = 100005;
const int MOD = 1000000007;
class cht {
private:
vector<long long> m, b;
int sz = 0;
bool test(int i, int j, int k) {
return (b[j]-b[i])*(m[k]-m[i]) > (b[k]-b[i])*(m[j]-m[i]);
}
long long eval(int i, long long x) {
return m[i]*x+b[i];
}
public:
int insert(long long mv, long long bv) {
sz++;
m.push_back(mv); b.push_back(bv);
int rem = 0;
while (sz >= 3 && !test(sz-3, sz-2, sz-1)) {
swap(m[sz-1], m[sz-2]);
swap(b[sz-1], b[sz-2]);
sz--;
rem++;
}
return rem;
}
long long query(long long x) {
int l = 0, r = sz-2;
while (l <= r) {
int mid = (l+r)/2;
if (eval(mid, x) > eval(mid+1, x)) {
l = mid+1;
} else {
r = mid-1;
}
}
return eval(l, x);
}
void rest(int cnt) {
m.erase(m.end()-cnt-1);
b.erase(b.end()-cnt-1);
sz += cnt-1;
}
void popLast() {
m.pop_back();
b.pop_back();
sz--;
}
};
int n;
vector<pair<int, ll>> adj[MAXN];
ll si[MAXN], vi[MAXN];
cht ch;
ll ans[MAXN];
void dfs(int x, int p, ll d) {
if (x != 1) ans[x] = ch.query(vi[x])+d*vi[x]+si[x];
int rem = ch.insert(-d, ans[x]);
for (auto pv : adj[x]) {
if (pv.first != p) {
dfs(pv.first, x, d+pv.second);
}
}
ch.rest(rem);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 0; i < n-1; i++) {
int u, v; ll d; cin >> u >> v >> d;
adj[u].push_back({v, d});
adj[v].push_back({u, d});
}
for (int i = 2; i <= n; i++) {
cin >> si[i] >> vi[i];
}
dfs(1, 1, 0);
for (int i = 2; i <= n; i++) {
cout << ans[i];
if (i < n) cout << " ";
}
cout << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2688 KB |
Output isn't correct |
| 2 |
Incorrect |
4 ms |
3308 KB |
Output isn't correct |
| 3 |
Incorrect |
51 ms |
11756 KB |
Output isn't correct |
| 4 |
Incorrect |
76 ms |
15840 KB |
Output isn't correct |
| 5 |
Incorrect |
111 ms |
20056 KB |
Output isn't correct |
| 6 |
Incorrect |
145 ms |
24044 KB |
Output isn't correct |
| 7 |
Incorrect |
70 ms |
12044 KB |
Output isn't correct |
| 8 |
Incorrect |
645 ms |
17248 KB |
Output isn't correct |
| 9 |
Execution timed out |
1082 ms |
13964 KB |
Time limit exceeded |
| 10 |
Incorrect |
100 ms |
17892 KB |
Output isn't correct |
