#include <bits/stdc++.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=native")
#define vi vector<int>
#define vb vector<bool>
#define vl vector<long long>
#define vii vector<vector<int>>
#define vll vector<vector<long long>>
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vpi vector<pair<int, int>>
#define vpl vector<pair<ll, ll>>
#define a first
#define b second
#define str string
#define pb push_back
#define hset unordered_set
#define hmap unordered_map
const int mod = 1e9+7;
const int mm = 998244353;
//16094558932
using namespace std;
using ll = long long;
using ull = unsigned ll;
const ll inf = LLONG_MAX>>2;
template<size_t SZ> struct RMQ {
static constexpr int level(int x) { return 31-__builtin_clz(x); }
array<array<int,SZ>, level(SZ)+1> jmp;
vi v;
void init(const vi& depth, const vi& ind){
v = depth;
assert(ind.size() <= SZ);
copy(begin(ind), end(ind), begin(jmp[0]));
for (int j = 1; 1<<j <= ind.size(); ++j)
for(int i = 0; i<ind.size()-(1<<j)+1; i++){
int a = jmp[j-1][i], b = jmp[j-1][i+(1<<(j-1))];
jmp[j][i] = depth[a] < depth[b] ? a:b;
}
}
int query(int l, int r) {
if(l > r) swap(l, r);
int d = level(r-l+1);
int a = jmp[d][l], b = jmp[d][r-(1<<d)+1];
return v[a] < v[b] ? a:b;
}
};
struct BIT {
int N; vl data;
void init(int sz){N = sz+1; data.resize(sz+1, 0); }
void add(int p, ll x) { for (p++;p<=N;p+=p&-p) data[p-1] = (data[p-1]+x); }
ll sum(int l, int r) { return sum(r)-(l==0?0:sum(l-1)); }
ll sum(int r) { ll s = 0; r++; for(;r;r-=r&-r)s = (s+data[r-1]); return s; }
int lower_bound(ll sum) {
if (sum <= 0) return -1;
int pos = 0;
for (int pw = 1<<25; pw; pw >>= 1) {
int npos = pos+pw;
if (npos <= N && data[npos-1] < sum)
pos = npos, sum -= data[pos-1];
}
return pos;
}
};
struct DSU {
vector<int> e;
DSU(int N) { e = vector<int>(N, -1); }
// get representive component (uses path compression)
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool same_set(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y) { // union by size
x = get(x), y = get(y);
if (x == y) return false;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y];
e[y] = x;
return true;
}
};
struct Hasher {
vl h1, h2, p1, p2, v1, v2;
const ll m1 = 1283, m2 = 2793;
const ll i1 = 439594703, i2 = 7876835;
Hasher(string s){
int n = s.size();
h1.resize(n);
h2.resize(n);
p1.resize(n);
p2.resize(n);
v1.resize(n);
v2.resize(n);
for(int i = 0; i<n; i++){
p1[i] = (i?p1[i-1]:i1)*m1%mod;
p2[i] = (i?p2[i-1]:i2)*m2%mod;
v1[i] = (i?v1[i-1]:m1)*i1%mod;
v2[i] = (i?v2[i-1]:m2)*i2%mod;
h1[i] = ((i?h1[i-1]:0)+p1[i]*(s[i]-'a'+1)%mod)%mod;
h2[i] = ((i?h2[i-1]:0)+p2[i]*(s[i]-'a'+1)%mod)%mod;
}
}
pi get(int l, int r){
ll a = (h1[r]-(l?h1[l-1]:0)+mod)%mod;
ll b = (h2[r]-(l?h2[l-1]:0)+mod)%mod;
return {(int)(a*v1[l]%mod), (int)(b*v2[l]%mod)};
}
};
struct SegTree {
vll mem;
int n;
public:
SegTree(int N){
n = N;
mem.resize(n<<1, vl(4));
}
void set(int ind, ll val){
for(mem[ind+=n] = {val,val,val,val}; ind>>=1;) mem[ind] = comb(mem[ind<<1], mem[ind<<1|1]);
}
ll get(int l, int r){
vl L = {}, R = {};
for(l+=n,r+=n+1;l<r;l>>=1,r>>=1){
if(l&1) L = comb(L, mem[l++]);
if(r&1) R = comb(mem[--r], R);
}
return comb(L, R)[0];
}
private:
vl comb(vl& l, vl& r){
if(l.size() == 0) return r;
if(r.size() == 0) return l;
return {max({l[0], r[0], l[2]+r[1]}),
max({l[3]+r[1], l[1]}),
max({r[3]+l[2], r[2]}),
l[3]+r[3]
};
}
};
class LZST {
private:
class Node {
public:
ll l, r;
Node *left, *right;
ll val = 0, max = 0, min = 0, add = 0;
bool isSet = false;
Node(ll a, ll b) : l(a), r(b), left(nullptr), right(nullptr) {}
void set(ll num) {
isSet = true;
add = max = min = num;
val = num * (r - l + 1);
}
void addF(ll num) {
add += num;
val += num * (r - l + 1);
max += num;
min += num;
}
void prop() {
ll mid = (l + r) >> 1;
if (left == nullptr) left = new Node(l, mid);
if (right == nullptr) right = new Node(mid + 1, r);
if (isSet) {
isSet = false;
if (l != r) {
left->set(add);
right->set(add);
}
} else if (add != 0) {
if (l != r) {
left->addF(add);
right->addF(add);
}
}
add = 0;
}
void upd() {
val = left->val + right->val;
min = std::min(left->min, right->min);
max = std::max(left->max, right->max);
}
};
Node* top;
void set(ll s, ll e, ll num, Node* curr) {
if (curr->l == s && curr->r == e) {
curr->set(num);
return;
}
curr->prop();
if (e <= curr->left->r) set(s, e, num, curr->left);
else if (s >= curr->right->l) set(s, e, num, curr->right);
else {
set(s, curr->left->r, num, curr->left);
set(curr->right->l, e, num, curr->right);
}
curr->upd();
}
void add(ll s, ll e, ll num, Node* curr) {
if (curr->l == s && curr->r == e) {
curr->addF(num);
return;
}
curr->prop();
if (e <= curr->left->r) add(s, e, num, curr->left);
else if (s >= curr->right->l) add(s, e, num, curr->right);
else {
add(s, curr->left->r, num, curr->left);
add(curr->right->l, e, num, curr->right);
}
curr->upd();
}
ll sum(ll s, ll e, Node* curr) {
if (curr->l == s && curr->r == e) return curr->val;
curr->prop();
if (e <= curr->left->r) return sum(s, e, curr->left);
if (s >= curr->right->l) return sum(s, e, curr->right);
return sum(s, curr->left->r, curr->left) + sum(curr->right->l, e, curr->right);
}
ll max(ll s, ll e, Node* curr) {
if (curr->l == s && curr->r == e) return curr->max;
curr->prop();
if (e <= curr->left->r) return max(s, e, curr->left);
if (s >= curr->right->l) return max(s, e, curr->right);
return std::max(max(s, curr->left->r, curr->left), max(curr->right->l, e, curr->right));
}
ll min(ll s, ll e, Node* curr) {
if (curr->l == s && curr->r == e) return curr->min;
curr->prop();
if (e <= curr->left->r) return min(s, e, curr->left);
if (s >= curr->right->l) return min(s, e, curr->right);
return std::min(min(s, curr->left->r, curr->left), min(curr->right->l, e, curr->right));
}
public:
LZST(ll N) {
assert(N > 0);
top = new Node(0, N - 1);
}
ll get(ll s) {
assert(s >= top->l && s <= top->r);
Node* curr = top;
stack<Node*> stk;
while (curr->l != curr->r) {
stk.push(curr);
curr->prop();
if (s <= curr->left->r) curr = curr->left;
else curr = curr->right;
}
while (!stk.empty()) stk.top()->upd(), stk.pop();
return curr->val;
}
ll sum(ll s, ll e) {
assert(s >= top->l && s <= top->r && e >= top->l && e <= top->r && s <= e);
return sum(s, e, top);
}
ll max(ll s, ll e) {
assert(s >= top->l && s <= top->r && e >= top->l && e <= top->r && s <= e);
return max(s, e, top);
}
ll min(ll s, ll e) {
assert(s >= top->l && s <= top->r && e >= top->l && e <= top->r && s <= e);
return min(s, e, top);
}
void add(ll s, ll e, ll num) {
assert(s >= top->l && s <= top->r && e >= top->l && e <= top->r && s <= e);
add(s, e, num, top);
}
void add(ll s, ll num) {
assert(s >= top->l && s <= top->r);
add(s, s, num, top);
}
void set(ll s, ll e, ll num) {
assert(s >= top->l && s <= top->r && e >= top->l && e <= top->r && s <= e);
set(s, e, num, top);
}
void set(ll s, ll num) {
assert(s >= top->l && s <= top->r);
set(s, s, num, top);
}
};
ll pow(ll num, ll k, int mod){
num%=mod;
ll ans = 1;
while(k > 0){
if(k&1) ans = ans*num%mod;
k>>=1;
num = num*num%mod;
}
return ans;
}
ll modInv(ll num, int mod){
return pow(num, mod-2, mod);
}
struct Line {
mutable ll k, m, p;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct LC : multiset<Line, less<>> {
ll div(ll a, ll b) {
return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
if (y == end()) return x->p = inf, 0;
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m) {
auto z = insert({k, m, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
ll max(ll x) {
if(empty()) return -inf;
auto l = *lower_bound(x);
return l.k * x + l.m;
}
};
const string name = "harbingers";
const int MAXN = 1e5;
vpi g[MAXN];
ll st[MAXN], go[MAXN], ans[MAXN];
int cnt[MAXN];
void dfs1(int s, int p){
cnt[s] = 1;
for(pi& i: g[s]) if(i.a != p){
dfs1(i.a, s);
cnt[s]+=cnt[i.a];
}
}
void dfs3(int s, int p, ll dis, LC& above){
ans[s] = min(ans[s], -above.max(-go[s])+st[s]+dis*go[s]);
for(pi& i: g[s]) if(i.a != p)
dfs3(i.a, s, dis+i.b, above);
}
void dfs2(int s, int p, ll dis, LC& above){
ans[s] = min(ans[s], -above.max(-go[s])+st[s]+dis*go[s]);
int max = -1;
ll b = 0;
for(pi& i: g[s]) if(i.a != p && (max == -1 || cnt[i.a] > cnt[max]))
max = i.a, b = i.b;
for(pi& i: g[s]) if(i.a != p && i.a != max){
dfs3(i.a, s, dis+i.b, above);
LC next;next.add(-dis, -ans[s]);
dfs2(i.a, s, dis+i.b, next);
}
if(max+1){
above.add(-dis, -ans[s]);
dfs2(max, s, dis+b, above);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if(filesystem::exists("input.in")) freopen("input.in", "r", stdin);
else if(name.size() && filesystem::exists(name+".in")){
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
int n; cin >> n;
for(int i = 1; i<n; i++){
int a, b, w; cin >> a >> b >> w;
g[--a].pb({--b, w});
g[b].pb({a, w});
ans[i] = inf;
}
for(int i = 1; i<n; i++) cin >> st[i] >> go[i];
dfs1(0, -1); LC top;
dfs2(0, -1, 0, top);
for(int i = 1; i<n; i++) cout << ans[i] << " ";
cout << "\n";
}
Compilation message
harbingers.cpp: In function 'int main()':
harbingers.cpp:358:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
358 | if(filesystem::exists("input.in")) freopen("input.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:360:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
360 | freopen((name+".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:361:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
361 | freopen((name+".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
5464 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 3 |
Correct |
28 ms |
10200 KB |
Output is correct |
| 4 |
Correct |
41 ms |
12832 KB |
Output is correct |
| 5 |
Correct |
48 ms |
13780 KB |
Output is correct |
| 6 |
Correct |
60 ms |
15700 KB |
Output is correct |
| 7 |
Correct |
40 ms |
10060 KB |
Output is correct |
| 8 |
Correct |
79 ms |
15308 KB |
Output is correct |
| 9 |
Correct |
70 ms |
17492 KB |
Output is correct |
| 10 |
Correct |
66 ms |
16080 KB |
Output is correct |
