#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> B;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=100100;
const ll inf=1e9+10;
int n,s[N],w[N],tsz;
ll dep[N],dp[N];
vector<PII> g[N];
struct line {
ll k,n;
line(ll _k=0LL,ll _n=0LL) : k(_k),n(_n) {}
ll calc(ll x) { return k*x+n; }
};
line stk[N];
struct op {
int tsz;
line ln;
};
stack<op> ops;
ll inter(line a,line b) {
/* x=(b.n-a.n)/(a.k-b.k); */
return (b.n-a.n)/(a.k-b.k);
}
pair<ll,ll> getrng(int idx) {
ll L=(idx==1?-inf:inter(stk[idx-1],stk[idx]));
if (idx>1) {
while (stk[idx-1].calc(L)<stk[idx].calc(L)) {
L+=1;
}
}
ll R=(idx==tsz?inf:inter(stk[idx],stk[idx+1]));
if (idx<tsz) {
while (stk[idx+1].calc(R+1)>=stk[idx].calc(R+1)) {
R+=1;
}
}
return mp(L,R);
}
void ins(line ln) {
if (stk[tsz].calc(inf)<ln.calc(inf)) {
ops.push({-1,line(0ll,0ll)});
return;
}
int low=1,high=tsz,pos=1;
while (low<=high) {
int mid=low+high>>1;
pair<ll,ll> rng=getrng(mid);
if (stk[mid].calc(rng.se)<ln.calc(rng.se)) {
low=mid+1;
} else {
if (stk[mid].calc(rng.fi)<ln.calc(rng.fi)) {
pos=mid+1;
break;
} else {
pos=mid;
high=mid-1;
}
}
}
ops.push({tsz,stk[pos]});
tsz=pos;
stk[pos]=ln;
}
void rem() {
if (ops.top().tsz==-1) {
tsz--;
ops.pop();
return;
}
stk[tsz]=ops.top().ln;
tsz=ops.top().tsz;
ops.pop();
}
ll query(ll x) {
int low=1,high=tsz-1,pos=tsz;
while (low<=high) {
int mid=low+high>>1;
pair<ll,ll> rng=getrng(mid);
if (rng.fi<=x&&x<=rng.se) {
pos=mid;
break;
}
if (x>rng.se) {
low=mid+1;
} else {
high=mid-1;
}
}
return stk[pos].calc(x);
}
void dfs(int v,int pv) {
if (v>1) {
dp[v]=query(w[v])+dep[v]*1ll*w[v]+s[v];
}
ins(line(-dep[v],dp[v]));
for (auto& e:g[v]) {
int u=e.fi,l=e.se;
if (u==pv) {
continue;
}
dep[u]=dep[v]+l;
dfs(u,v);
}
rem();
}
int main() {
scanf("%d",&n);
rep(i,1,n) {
int u,v,d;
scanf("%d%d%d",&u,&v,&d);
g[u].pb(mp(v,d));
g[v].pb(mp(u,d));
}
rep(i,2,n+1) {
scanf("%d%d",s+i,w+i);
}
dfs(1,0);
rep(i,2,n+1) printf("%lld ",dp[i]);
}
Compilation message
harbingers.cpp: In function 'void ins(line)':
harbingers.cpp:72:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
72 | int mid=low+high>>1;
| ~~~^~~~~
harbingers.cpp: In function 'll query(ll)':
harbingers.cpp:105:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
105 | int mid=low+high>>1;
| ~~~^~~~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:137:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
harbingers.cpp:140:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
140 | scanf("%d%d%d",&u,&v,&d);
| ~~~~~^~~~~~~~~~~~~~~~~~~
harbingers.cpp:145:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
145 | scanf("%d%d",s+i,w+i);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5052 KB |
Output is correct |
| 3 |
Correct |
41 ms |
10552 KB |
Output is correct |
| 4 |
Correct |
65 ms |
13556 KB |
Output is correct |
| 5 |
Correct |
61 ms |
16396 KB |
Output is correct |
| 6 |
Correct |
68 ms |
19104 KB |
Output is correct |
| 7 |
Correct |
47 ms |
11084 KB |
Output is correct |
| 8 |
Correct |
104 ms |
14752 KB |
Output is correct |
| 9 |
Correct |
102 ms |
16468 KB |
Output is correct |
| 10 |
Correct |
111 ms |
15508 KB |
Output is correct |
