#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#define foreach for
#define in :
using namespace std;
typedef long long ll;
int MODULO =1e9+7 ;
const long long INF = 1e18+7;
const unsigned long long LIMIT = 2e18;
/*
Konichiwa
Konichiwa
Ara ~~ ara
Bob no taisuki - Shinobu Kocho
* * * * *
* *
* *
* * I love SHINOBU <3 <3 <3
* *
* *
* * * * *
*/
/*
_________________________
Author : Bob15324
_________________________
*/
/*
okay i'm hoping that somebody pray for me
I'm praying that somebody hope for me
I'm staying where nobody 'posed to be
p-p-posted
being a wreak of emotions
ready to go whenever just let me know
the road is long so put the pedal into the floor
the enemy's on my trail
my energy unavailble
Imma tell em hasta luego
they wanna plot on my trot to the top
I've been outta shape thinking out the box I'm an astronaut
i balsted off the planet rock to cause catastrophe and it matters
more because i had it not
had i thought about wreaking havoc on an opposition
kinda shocking they wanted static
with precision i'm automatic quarterback
i ain't talking sacking pack itpack it up i don't panic
who the baddest it doesn't matter cause we at ya throat
*/
// EVERYBODY WANT TO BE MY ENEMY
template<class X , class Y>
bool Minimize(X & x , Y y)
{
if( x > y )
{
x = y;
return true;
}
return false;
}
template<class X , class Y>
bool Maximize(X & x , Y y)
{
if( x < y)
{
x = y;
return true;
}
return false;
}
template<class X , class Y>
void Add(X &x , Y y )
{
x += y;
if(x >= MODULO)
{
x -= MODULO;
}
}
template<class X , class Y>
void Sub(X &x ,Y y)
{
x -= y;
if(x < 0)
{
x += MODULO;
}
}
template<class X , class Y>
bool Check_MUL(X x , Y y )
{
return x > LIMIT/y;
}
/* End of templates. Let's see what do we have here */
const int N = 1e5+1;
int n ;
vector<pair<int ,int >>vertices[N];
struct mailer
{
int s , v;
mailer(int _s ,int _v)
{
s = _s;
v = _v;
}
mailer()
{
s = 0;
v = 0;
}
}mail[N];
struct Lines
{
long long a , b ;
int u ;
Lines(long long _a , long long _b ,int _u)
{
a = _a;
b = _b;
u = _u;
}
long long operator() (long long x) const {return a * x + b;}
};
deque<Lines>dq;
bool bad(Lines &l1 , Lines &l2 , Lines & l3)
{
return (long double) (l3.b - l1.b) *(l1.a - l2.a) < (long double) (l2.b - l1.b) *(l1.a - l3.a);
}
void add(Lines line , vector<Lines> & List)
{
while((int)dq.size() >= 2 && bad(dq[(int)dq.size() - 2] , dq[(int)dq.size()-1] , line) )
{
List.push_back(dq.back());
dq.pop_back();
}
dq.push_back(line);
}
long long Get(long long x , vector<Lines> &List)
{
while((int)dq.size() >= 2 && dq[0] (x) <= dq[1](x) )
{
List.push_back(dq.front());
dq.pop_front();
}
return dq.front()(x);
}
void del(int u)
{
if(dq.back().u == u)
{
dq.pop_back();
return ;
}
assert(false);
}
long long ans[N];
long long dist[N];
void DFS(int u ,int daddy)
{
vector<Lines>get , d;
ans[u] = dist[u] * 1LL * mail[u].v - Get(mail[u].v , get) + mail[u].s ;
add(Lines( dist[u] , -ans[u] , u) ,d);
foreach(pair<int ,int >&adj in vertices[u])
{
int v = adj.first;
int w = adj.second;
if(v == daddy)continue;
dist[v] = dist[u] + w;
DFS(v ,u );
}
del(u);
foreach(Lines &l in d)dq.push_back(l);
foreach(Lines &l in get)dq.push_front(l);
}
void Input()
{
cin >> n ;
for(int i =1 ; i <= n-1 ; i++)
{
int u , v , w;
cin >> u >> v >> w;
vertices[u].push_back(make_pair(v , w));
vertices[v].push_back(make_pair(u , w));
}
mail[1] = mailer(0 , 0);
for(int i =2 ; i <= n ; i++)
{
cin >> mail[i].s >> mail[i].v;
}
}
void Process()
{
dq.push_back(Lines(0 , 0, 1));
foreach(pair<int ,int >& adj in vertices[1])
{
int v = adj.first;
int w = adj.second;
dist[v] = w;
DFS(v , 1);
//assert(dq.front().a == 0 && dq.front().b == 0 && dq.front().u == 1 && (int)dq.size() == 1);
}
for(int i =2 ; i <= n ; i++)cout << ans[i] <<' ';
}
int main()
{
ios_base :: sync_with_stdio(0);cin.tie(0);
int test;
test = 1;
while(test--)
{
Input();
Process();
cout <<'\n';
}
return 0;
}
//Ehem. My code is amazing. Pay me 2$.Thank you.
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
6868 KB |
Execution killed with signal 6 |
| 2 |
Runtime error |
8 ms |
8148 KB |
Execution killed with signal 6 |
| 3 |
Runtime error |
42 ms |
28364 KB |
Execution killed with signal 6 |
| 4 |
Runtime error |
59 ms |
39112 KB |
Execution killed with signal 6 |
| 5 |
Runtime error |
84 ms |
50020 KB |
Execution killed with signal 6 |
| 6 |
Runtime error |
118 ms |
60912 KB |
Execution killed with signal 6 |
| 7 |
Runtime error |
56 ms |
13760 KB |
Execution killed with signal 6 |
| 8 |
Runtime error |
84 ms |
34460 KB |
Execution killed with signal 6 |
| 9 |
Incorrect |
84 ms |
22552 KB |
Output isn't correct |
| 10 |
Runtime error |
93 ms |
39272 KB |
Execution killed with signal 6 |
