// // #pragma GCC optimize("Ofast")
// #include <bits/stdc++.h>
// using namespace std;
// template<int SZ> struct Tree {
// vector<pair<int,int>> adj[SZ];
// void init(int n) {
// for (int i = 0; i < n-1; i++) {
// int a, b, c; cin >> a >> b >> c; a--, b--;
// adj[a].push_back({b,c});
// adj[b].push_back({a,c});
// }
// }
// };
// #define f first
// #define s second
// const int maxn = 100005;
// int n;
// Tree<maxn> tree;
// pair<int,int> v[maxn];
// int dist[maxn];
// int ans[maxn];
// struct F {
// int a, b;
// F() {}
// F(int A, int B) : a(A), b(B) { if (b<0) a*=-1, b*=-1; }
// bool operator<(F o) const { return a*o.b < b*o.a; }
// bool operator<=(F o) const { return a*o.b <= b*o.a; }
// };
// struct L {
// int m, b;
// int operator()(int x) { return m*x + b; }
// F operator^(L o) { return F{b-o.b,o.m-m}; }
// };
// struct ND {
// L v;
// ND *l, *r;
// ND(int m, int b) { v = L{m, b}; l = r = nullptr; }
// ND(ND* _l, ND* _r) { v = L{0, 0}; _l = _r = nullptr; }
// };
// struct Node {
// L v;
// Node *l, *r;
// Node(L x) : v(x), l(nullptr), r(nullptr) {}
// Node(Node* _l, Node* _r) : l(_l), r(_r) { v = L{0ll, 0ll}; }
// };
// template<int SZ> struct PersArray {
// Node* roots[SZ];
// int end[SZ];
// Node* build(int l, int r) {
// if (l == r) { return new Node(L{0ll, 0ll}); }
// int m = (l + r) >> 1;
// return new Node(build(l, m), build(m+1, r));
// }
// void init() { roots[0] = build(0, n-1); }
// Node* UPD(Node* nd, int K, L V, int l, int r) {
// if (l == r) { return new Node(V); }
// int m = (l + r) >> 1;
// if (K <= m) return new Node(UPD(nd->l, K, V, l, m), nd->r);
// else return new Node(nd->l, UPD(nd->r, K, V, m+1, r));
// }
// L QRY(Node* nd, int K, int l, int r) {
// if (l == r) return nd->v;
// int m = (l + r) >> 1;
// if (K <= m) return QRY(nd->l, K, l, m);
// else return QRY(nd->r, K, m+1, r);
// return L{0ll, 0ll};
// }
// inline L qry(int K, int T) {
// return QRY(roots[T], K, 0, n-1);
// }
// inline void upd(int K, L V, int T, int Tp) {
// roots[T] = UPD(roots[Tp], K, V, 0, n-1);
// }
// };
// struct CHT {
// PersArray<maxn> pers;
// void add(int nd, int par, L l) {
// int sz = pers.end[par];
// while (sz >= 2 && (pers.qry(sz-2,par) ^ l) <= (pers.qry(sz-2,par) ^ pers.qry(sz-1, par)))
// sz--;
// pers.upd(sz, l, nd, par);
// pers.end[nd] = sz + 1;
// }
// int qry(int nd, int x) {
// int lo = 0, hi = pers.end[nd]-1;
// while (lo < hi) {
// int m = (lo + hi) >> 1;
// if (pers.qry(m, nd)(x) > pers.qry(m+1, nd)(x))
// lo = m+1;
// else
// hi = m;
// }
// return (pers.qry(lo, nd))(x);
// }
// };
// CHT cht;
// int cnt = 0;
// void dfs(int nd, int par, int parst) {
// int cur = cnt++;
// if (nd != 0)
// ans[nd] = v[nd].f + v[nd].s * dist[nd] + cht.qry(parst, v[nd].s);
// cht.add(cur, parst, L{-dist[nd], ans[nd]});
// for (auto i : tree.adj[nd])
// if (i.f != par) {
// dist[i.f] = dist[nd] + i.s;
// dfs(i.f, nd, cur);
// }
// }
// signed main() {
// cin.tie(nullptr) -> ios::sync_with_stdio(false);
// // freopen("main.in", "r", stdin);
// cin >> n;
// tree.init(n);
// for (int i = 1; i < n; i++) cin >> v[i].f >> v[i].s;
// cht.pers.init();
// dfs(0, 0, 0);
// for (int i = 1; i < n; i++)
// cout << ans[i] << ' ';
// cout << endl;
// return 0;
// }
/************ PERSISTANT ARRAY ALGO ABOVE, EXCEEDS TIME DUE TO CONSTANTS AND ALSO MEMORY **************/
/************ CHT ALGO BELOW, PASSES **************/
// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
struct F {
int a, b;
F() {}
F(int A, int B) : a(A), b(B) { if (b<0) a*=-1, b*=-1; }
bool operator<(F o) const { return a*o.b < b*o.a; }
bool operator<=(F o) const { return a*o.b <= b*o.a; }
};
struct L {
int m, b;
int operator()(int x) { return m*x + b; }
F operator^(L o) { return F{b-o.b,o.m-m}; }
};
const int maxn = 100000;
int n;
vector<pair<int,int>> adj[maxn];
pair<int,int> v[maxn];
pair<int,L> removed[maxn];
int ans[maxn];
L CHT[maxn]; int cht_sz = 0;
void add(L l, int nd) {
removed[nd] = {cht_sz, l};
int lo = 0, hi = cht_sz - 1; // represents range for rightmost OLD ONE
while (lo < hi) {
int mid = (lo + hi) >> 1; // will test MID & (MID+1)
if ((CHT[mid]^l) <= (CHT[mid]^CHT[mid+1]))
hi = mid;
else
lo = mid+1;
}
cht_sz = lo+1;
// while (cht_sz >= 2 && (CHT[cht_sz-2]^l) <= (CHT[cht_sz-2]^CHT[cht_sz-1]))
// cht_sz--;
swap(removed[nd].s, CHT[cht_sz++]);
}
int qry(int x) {
int lo = 0, hi = cht_sz-1;
while (lo < hi) {
int m = (lo + hi) >> 1;
if (CHT[m](x) > CHT[m+1](x))
lo = m+1;
else
hi = m;
}
return CHT[lo](x);
}
void restore(int nd) {
cht_sz--;
swap(removed[nd].s, CHT[cht_sz]);
cht_sz = removed[nd].f;
}
void dfs(int nd, int par, int d) {
add(L{-d, ans[nd]}, par);
for (auto i : adj[nd])
if (i.f != par) {
ans[i.f] = v[i.f].f + v[i.f].s * (d + i.s) + qry(v[i.f].s);
dfs(i.f, nd, d + i.s);
}
restore(par);
}
signed main() {
// freopen("main.in", "r", stdin);
cin >> n;
for (int i = 0; i < n-1; i++) {
int a, b, c; 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 >> v[i].f >> v[i].s;
dfs(0, 0, 0);
for (int i = 1; i < n; i++) cout << ans[i] << ' ';
cout << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7204 KB |
Output is correct |
| 3 |
Incorrect |
59 ms |
13448 KB |
Output isn't correct |
| 4 |
Correct |
84 ms |
17124 KB |
Output is correct |
| 5 |
Correct |
128 ms |
19884 KB |
Output is correct |
| 6 |
Correct |
134 ms |
22608 KB |
Output is correct |
| 7 |
Correct |
80 ms |
13904 KB |
Output is correct |
| 8 |
Incorrect |
133 ms |
18376 KB |
Output isn't correct |
| 9 |
Correct |
140 ms |
20164 KB |
Output is correct |
| 10 |
Correct |
132 ms |
18632 KB |
Output is correct |
