#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define foru(i, a, b, k) for(int i = a; i <= b; i += k)
#define umap unordered_map
#define pii pair<int, int>
#define ford(i, a, b, k) for(int i = a; i >= b; i -= k)
#define vint vector <int>
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second
#define pb push_back
#define sz(s) (int)s.size()
#define ctn continue
#define ld long double
void read();
void solve();
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
template<typename T> ll power(T a, const T b) { ll res = 1, x = a, y = b; while(y){if(y & 1)res *= x; x = x * x; y>>=1;}; return res; }
template<typename T> ll modpower(T a, T b, const T &m) { ll res = 1, x = a, y = b; x %= m; while(y){if(y & 1){res *= x; res %= m;}; x = x * x; x %= m; y >>= 1; } return res % m; }
template<typename T> T __lcm(T &a, T &b) { return a / __gcd(a, b) * b; }
template <typename T> bool getbit(T val, int i) { return (val >> i) & 1; }
template <typename T> int cntbit(T val) { int cnt = 0; for( ; val; val -= val & (-val)) ++cnt; return cnt; }
template <typename T> T offbit(T val, int i) { return val & (~(T(1) << i)); }
template <typename T> T onbit(T val, int i) { return val | (T(1) << i); }
inline int readInt() {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong() {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
template <typename _Tp> void write_unsign(const _Tp &__n) { if (__n > 9) { write_unsign(__n / 10); } putchar(__n % 10 + '0'); }
void write(const int &__n) { if (__n < 0) { putchar('-'); write_unsign(-__n); } else { write_unsign(__n); } }
void write(const long long &__n) { if (__n < 0) { putchar('-'); write_unsign(-__n); } else { write_unsign(__n); } }
void write(const unsigned long long &__n) { if (__n < 0) { putchar('-'); write_unsign(-__n); } else { write_unsign(__n); } }
void write(const char &__c) { putchar(__c); }
void write(const string &__s) { for (auto &__c : __s) { putchar(__c); } }
template <typename _Tp, typename... _Ts> void write(const _Tp &__x, const _Ts &...__y) { write(__x), write(__y...); }
#define int ll
const ll MOD = 1e9 + 7;
const ll LIM = (1 << 10) + 5;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll LINF = 1e17 + 100;
const int LOG = 19;
const ll base = 31;
const int offset = 1e6 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int mul(int a, int b) { return 1LL * a * b % MOD; }
// #define Ckn_calc
#ifdef Ckn_calc
const int Mod = MOD;
int fact[LIM + 10]; /// factorial: fact[n] = n!
int invs[LIM + 10]; /// inverse modular: invs[n] = n^(-1)
int tcaf[LIM + 10]; /// inverse factorial: tcaf[n] = (n!)^(-1)
void precal_nck(int n = LIM)
{
fact[0] = fact[1] = 1;
invs[0] = invs[1] = 1;
tcaf[0] = tcaf[1] = 1;
for (int i = 2; i <= n; ++i)
{
fact[i] = (1LL * fact[i - 1] * i) % MOD;
invs[i] = MOD - 1LL * (MOD / i) * invs[MOD % i] % MOD;
tcaf[i] = (1LL * tcaf[i - 1] * invs[i]) % MOD;
}
}
ll C(int n, int k) {
if(min(n, k) < 0 || n < k) return 0;
ll res = fact[n];
res *= tcaf[k], res %= Mod;
res *= tcaf[n - k], res %= Mod;
return res;
}
ll P(int n, int k) {
ll res = fact[n];
res *= tcaf[n - k], res %= Mod;
return res;
}
#endif
struct Line
{
ll m, b;
Line() { }
Line(ll _m, ll _b) : m(_m), b(_b) { };
ll operator () (ll x) { return m * x + b; }
friend ld intersect(const Line &l1, const Line &l2)
{
return (ld)(l2.b - l1.b) / (ld)(l1.m - l2.m);
}
};
Line stk[N];
int stk_max = 0;
int n;
vector < vector <pii> > g;
ll f[N], v[N], s[N];
ll query(ll x)
{
int l = 0, r = stk_max - 1, mid;
while(l < r)
{
mid = l + r >> 1;
if(intersect(stk[mid], stk[mid + 1]) < x) l = mid + 1;
else r = mid;
}
return stk[l](x);
}
ll remove(Line line)
{
if(stk_max < 2 || intersect(line, stk[stk_max - 1]) >= intersect(stk[stk_max - 1], stk[stk_max - 2]))
return stk_max;
int l = 1, r = stk_max - 1;
while(l < r)
{
int mid = l + r >> 1;
if(intersect(line, stk[mid]) < intersect(stk[mid], stk[mid - 1])) r = mid;
else l = mid + 1;
}
return l;
}
void dfs(int u, int par, ll d)
{
int premax, prepos;
Line preline;
if(u == par)
{
f[u] = 0;
stk[stk_max++] = Line(0, 0);
}
else
{
f[u] = query(v[u]) + d * v[u] + s[u];
Line l(- d, f[u]);
premax = stk_max;
prepos = stk_max = remove(l);
preline = stk[stk_max];
stk[stk_max++] = l;
}
for(auto &[v, w] : g[u]) if(v != par)
dfs(v, u, d + w);
if(u != par)
{
stk_max = premax;
stk[prepos] = preline;
}
}
void read()
{
n = readInt();
g.resize(n + 5);
foru(i, 1, n - 1, 1)
{
int u, v, w;
u = readInt();
v = readInt();
w = readInt();
g[u].pb(make_pair(v, w));
g[v].pb(make_pair(u, w));
}
foru(i, 2, n, 1)
{
s[i] = readInt();
v[i] = readInt();
}
}
void solve()
{
dfs(1, 1, 0);
foru(i, 2, n, 1) cout << f[i] << " ";
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
#define file "test"
if(fopen(file".inp", "r"))
{
freopen(file".inp", "r", stdin);
freopen(file".out", "w", stdout);
}
read();
solve();
return 0;
}
Compilation message
harbingers.cpp: In function 'long long int query(long long int)':
harbingers.cpp:122:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
122 | mid = l + r >> 1;
| ~~^~~
harbingers.cpp: In function 'long long int remove(Line)':
harbingers.cpp:140:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
140 | int mid = l + r >> 1;
| ~~^~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:218:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
218 | freopen(file".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:219:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
219 | freopen(file".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
852 KB |
Output is correct |
| 3 |
Correct |
28 ms |
10708 KB |
Output is correct |
| 4 |
Correct |
39 ms |
15452 KB |
Output is correct |
| 5 |
Correct |
54 ms |
19996 KB |
Output is correct |
| 6 |
Correct |
90 ms |
24468 KB |
Output is correct |
| 7 |
Correct |
26 ms |
12356 KB |
Output is correct |
| 8 |
Correct |
87 ms |
18992 KB |
Output is correct |
| 9 |
Correct |
69 ms |
21024 KB |
Output is correct |
| 10 |
Correct |
63 ms |
19368 KB |
Output is correct |
