#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define taskname "HARBINGERS"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
const int maxn = 1e5 + 5;
vector<ii> adj[maxn];
ii a[maxn];
ll f[maxn];
int p[maxn];
ll dep[maxn];
int n;
int nTime = 0 , in[maxn] , out[maxn];
struct point{
ll x , y;
point(){};
point(ll x , ll y):x(x),y(y){};
point operator - (const point & other){
return point(x - other.x , y - other.y);
}
ll operator * (const point & other){
return x * other.y - y * other.x;
}
ll Val(int k){
return x * k + y;
}
};
bool ccw(point a , point b , point c){
return (a - b) * (c - b) <= 0;
}
struct convex{
vector<point> p;
void add(point now){
if(p.size() && now.x == p.back().x && now.y > p.back().y){
return;
}
while(p.size() >= 2 && ccw(p[p.size() - 2],p[p.size() - 1],now))
p.pop_back();
p.pb(now);
}
ll query(int x){
if(p.size() == 0)return 1e18;
int l = 0 , h = p.size() - 1;
while(l <= h){
int mid = l + h >> 1;
if(mid + 1 < p.size() && p[mid].Val(x) >= p[mid + 1].Val(x)){
l = mid + 1;
}else{
h = mid - 1;
}
}
return p[l].Val(x);
}
}s[maxn * 4];
void dfs1(int u , int par){
in[u] = ++nTime;
for(auto c : adj[u]){
if(c.first != par){
dfs1(c.first , u);
}
}
out[u] = nTime;
}
void update(int x , int l , int r , int L , int R , point now){
if(L > r || l > R)return;
if(L <= l && r <= R){
s[x].add(now);
return;
}
int mid = l + r >> 1;
update(x * 2 , l , mid , L , R , now);
update(x * 2 + 1 , mid + 1 , r , L , R , now);
}
ll query(int x , int l , int r , int pos , int k){
if(l == r)return s[x].query(k);
int mid = l + r >> 1;
if(mid >= pos)return min(s[x].query(k),query(x*2,l,mid,pos,k));
return min(s[x].query(k),query(x*2+1,mid+1,r,pos,k));
}
void dfs(int u,int par){
f[u] = 1e18;
if(u == 1)f[u] = 0;
else{
f[u] = query(1,1,n,in[u],a[u].second) + a[u].first + dep[u] * a[u].second;
}
update(1,1,n,in[u],out[u],point(-dep[u],f[u]));
for(ii c : adj[u]){
if(c.first == par)continue;
dep[c.first] = dep[u] + c.second;
dfs(c.first , u);
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen(taskname".IN","r")){
freopen(taskname".IN","r",stdin);
freopen(taskname".OUT","w",stdout);
}
cin >> n;
for(int i = 1 ; i < n ; ++i){
int u , v , c;cin >> u >> v >> c;
adj[u].pb(mp(v,c));adj[v].pb(mp(u,c));
}
for(int i = 2 ; i <= n ; ++i)cin >> a[i].first >> a[i].second;
dfs1(1,0);
dfs(1,0);
for(int i = 2 ; i <= n ; ++i)cout << f[i] << " ";
}
Compilation message
harbingers.cpp: In member function 'll convex::query(int)':
harbingers.cpp:49:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + h >> 1;
~~^~~
harbingers.cpp:50:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(mid + 1 < p.size() && p[mid].Val(x) >= p[mid + 1].Val(x)){
~~~~~~~~^~~~~~~~~~
harbingers.cpp: In function 'void update(int, int, int, int, int, point)':
harbingers.cpp:76:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
harbingers.cpp: In function 'll query(int, int, int, int, int)':
harbingers.cpp:82:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(taskname".IN","r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(taskname".OUT","w",stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
12280 KB |
Output is correct |
| 2 |
Correct |
17 ms |
12668 KB |
Output is correct |
| 3 |
Correct |
110 ms |
22264 KB |
Output is correct |
| 4 |
Correct |
163 ms |
28532 KB |
Output is correct |
| 5 |
Correct |
219 ms |
31144 KB |
Output is correct |
| 6 |
Runtime error |
267 ms |
35192 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 7 |
Correct |
167 ms |
25228 KB |
Output is correct |
| 8 |
Runtime error |
253 ms |
35504 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 9 |
Runtime error |
292 ms |
47052 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 10 |
Runtime error |
254 ms |
45364 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
