#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
#define forR(i, a) for(int i = 0; (i) < (a); ++(i))
#define REP(i, a, b) for(int i = (a); (i) < (b); ++i)
#define all(a) a.begin(), a.end()
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define printArr(arr) for(int asdfg : arr) cout << asdfg << ' '; cout << '\n'
#define open(x) freopen(((string) x + ".in").c_str(), "r", stdin); freopen(((string) x + ".out").c_str(), "w", stdout);
typedef long long ll;
typedef long double ld;
struct pii{ll a, b;};
struct tii{ll a, b, c;};
bool operator <(pii a, pii b){ return a.a < b.a || a.a == b.a && a.b < b.b;}
ll aOff=0, bOff=0;
class line{
private:
ll ar, br;
public:
line(ll a, ll b){
this->ar = a - aOff;
this->br = b - bOff;
}
line(){}
ll a(){return ar+aOff;}
ll b(){return br+bOff;}
ll ev(ll x){return a() * x + b();}
};
ld intX(line a, line b){
return (ld) (a.b()-b.b()) / (b.a() - a.a());
}
const int MN = 1e5 + 10, ME=20;
struct edge{int t, e;};
vector<edge> adj[MN];
int nex[MN][ME], ci=0; // one before next, array in increasing slope
line lin[MN];
ll ans[MN], s[MN], v[MN];
ll bes(ll x, int cur){
ll ret = lin[cur].ev(x);
for(int e = ME - 1; e >= 0; --e){
int las = nex[cur][e];
ret = min(ret, lin[las].ev(x));
if(nex[las][0] != -1 && lin[las].ev(x) > lin[nex[las][0]].ev(x)) cur = nex[las][0];
}
ret = min(ret, lin[cur].ev(x));
return ret;
}
void add(line toAdd, int firs){
lin[ci] = toAdd;
while(firs != -1 && nex[firs][0] != -1 && intX(toAdd, lin[firs]) < intX(lin[firs], lin[nex[firs][0]])) firs=nex[firs][0];
nex[ci][0] = firs;
REP(e, 1, ME) nex[ci][e] = nex[ci][e-1] == -1 ? -1 : nex[nex[ci][e-1]][e-1];
ci++;
}
void dfs(int c, int p, int st){
if(c != 1) ans[c] = bes(v[c], st) + s[c];
for(auto [t, e] : adj[c]) if(t != p){
aOff += e;
line eLine(e, ans[c]);
add(eLine, st);
dfs(t, c, ci - 1);
aOff -= e;
}
}
signed main(){
boost();
int n; cin >> n;
forR(e, n - 1){
int a, b, d; cin >> a >> b >> d;
adj[a].push_back({b, d});
adj[b].push_back({a, d});
}
REP(i, 2, n + 1) cin >> s[i] >> v[i];
dfs(1, -1, -1);
REP(i, 2, n + 1) cout << ans[i] << " \n"[i == n];
}
Compilation message
harbingers.cpp: In function 'bool operator<(pii, pii)':
harbingers.cpp:16:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
16 | bool operator <(pii a, pii b){ return a.a < b.a || a.a == b.a && a.b < b.b;}
| ~~~~~~~~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
4 ms |
3284 KB |
Output is correct |
3 |
Correct |
50 ms |
12328 KB |
Output is correct |
4 |
Correct |
70 ms |
17080 KB |
Output is correct |
5 |
Correct |
92 ms |
21592 KB |
Output is correct |
6 |
Correct |
106 ms |
26092 KB |
Output is correct |
7 |
Correct |
71 ms |
15936 KB |
Output is correct |
8 |
Execution timed out |
1084 ms |
16484 KB |
Time limit exceeded |
9 |
Correct |
239 ms |
23652 KB |
Output is correct |
10 |
Correct |
167 ms |
22916 KB |
Output is correct |