#include <bits/stdc++.h>
#define pb push_back
#define vii vector<int>
#define task "fencing"
#define pll pair<ll, ll>
#define pii pair< ll, pair< ll, ll > >
#define fi first
#define se second
using ll = long long;
using ld = long double;
using ull = unsigned long long;
const ll mod = 1e16+7;
using namespace std;
const ll N = 1e5 + 5;
ll tong, m, n, k, ans, t, a[N], b[N], c[N], u, v, cnt, top[N], chain, nchain[N], in[N], sz[N], d[N], par[N];
pll p[N];
//bool check;
string s;
vector<pll> pre, adj[N];
struct line
{
ll x, y;
line() {}
line(ll x, ll y) : x(x), y(y){}
long double inter(const line& v)const
{
return (long double) (v.y-y) * 1.0 / (x-v.x);
}
bool cross(const line& p, const line& q) const
{
return (long double) (q.y-y) * 1.0 / (x-q.x) - (p.y-y) * 1.0 / (x-p.x) <= 0;
//return 1.0 * (q.y - y) / (x - q.x) - 1.0 * (p.y - y) / (x - p.x) >= 0;
}
ll get(ll val)
{
return val * x + y;
}
};
vector<line> st[N*4];
void add(ll id, line d)
{
while(st[id].size() > 1 && st[id][st[id].size()-2].cross(st[id].back(), d))st[id].pop_back();
//while(!st[id].empty() && st[id].back().x == d.x)st[id].pop_back();
st[id].pb(d);
}
ll cal(ll id, ll x)
{
if(st[id].empty())return mod;
ll lf = 1, rt = st[id].size()-1, mid;
while(lf <= rt)
{
mid = (lf + rt) / 2;
if(mid < st[id].size() && st[id][mid-1].get(x) > st[id][mid].get(x))lf = mid + 1;
else rt = mid - 1;
}
return st[id][lf-1].get(x);
}
void update(ll id, ll l, ll r, ll pos, line d)
{
add(id, d);
if(l == r)return;
ll mid = (l + r) /2;
if(mid >= pos)update(id*2, l, mid, pos ,d);
else update(id*2+1, mid+1, r, pos ,d);
}
ll get(ll id, ll l, ll r, ll u, ll v, ll x)
{
if(l > v || u > r || u > v)return mod;
if(u <= l && r <= v)return cal(id, x);
ll mid = (l + r ) / 2;
return min(get(id*2, l, mid, u, v, x), get(id*2+1, mid+1, r, u, v, x));
}
void dfs(ll u, ll p)
{
sz[u] = 1;
for(pll v : adj[u])
{
if(v.se == p)continue;
d[v.se] = d[u] + v.fi;
par[v.se] = u;
dfs(v.se, u);
sz[u] += sz[v.se];
}
}
void getans(ll u, ll xi, ll yi)
{
ll rt = u;
//cout << u << '\n';
ll x = nchain[u], y = nchain[1];
ll total = mod;
while(x != y)
{
total = min(total, get(1, 1, n, in[top[x]], in[u], xi));
u = par[top[x]];
x = nchain[u];
}
c[rt] = min(total, get(1, 1, n, 1, in[u], xi))+ d[rt] * xi;
//cout << c[u] <<" " << yi << '\n';
c[rt] += yi;
update(1, 1, n, in[rt], line(-d[rt], c[rt]));
//cout << c[u] << " " << u << '\n';
}
void hld(ll u, ll pa)
{
//cout << u <<" "<<k+1<<'\n';
if(top[chain] == 0)top[chain] = u;
nchain[u] = chain;
in[u] = ++k;
//cout << u <<endl;
if(u > 1)getans(u, p[u].se, p[u].fi);
else update(1, 1, n, 1, line(0, 0));
//cout << u << endl;
ll big = -1;
for(pll v : adj[u])
{
if(v.se == pa)continue;
if(big == -1 || sz[v.se] > sz[big])big = v.se;
}
if(big != -1)hld(big, u);
for(pll v : adj[u])
{
if(v.se == pa || v.se == big)continue;
++chain;
hld(v.se, u);
}
}
void sol()
{
cin >> n;
for(int i = 1; i < n; i ++)
{
ll x, y, w;
cin >> x >> y >> w;
adj[x].pb({w, y});
adj[y].pb({w, x});
}
for(int i = 2; i <= n; i ++)cin >> p[i].fi >> p[i].se;
dfs(1, 0);
hld(1, 0);
for(int i = 2; i <= n; i ++)cout << c[i] << ' ';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen(task".in", "r"))
{
freopen(task".in", "r", stdin);
freopen(task".out", "w", stdout);
}
int ntest;
ntest = 1;
//cin >> ntest;
while(ntest -- > 0)
sol();
}
/*
5
1 3
2 -3
3 -5
0 3
1 10
6
? 1
+ 2 4 10 -10
? 2
? 3
? 4
+ 4 1 9 12
3
1 2
4 6
2 5
4
+ 1 1 -1 2
+ 1 2 -2 3
+ 1 3 1 0
? 1
*/
Compilation message
harbingers.cpp: In function 'll cal(ll, ll)':
harbingers.cpp:57:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | if(mid < st[id].size() && st[id][mid-1].get(x) > st[id][mid].get(x))lf = mid + 1;
| ~~~~^~~~~~~~~~~~~~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:156:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
156 | freopen(task".in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:157:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
157 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 2 |
Correct |
13 ms |
12908 KB |
Output is correct |
| 3 |
Correct |
108 ms |
25836 KB |
Output is correct |
| 4 |
Runtime error |
178 ms |
35808 KB |
Memory limit exceeded |
| 5 |
Runtime error |
223 ms |
37100 KB |
Memory limit exceeded |
| 6 |
Runtime error |
282 ms |
42836 KB |
Memory limit exceeded |
| 7 |
Correct |
190 ms |
31340 KB |
Output is correct |
| 8 |
Runtime error |
311 ms |
55004 KB |
Memory limit exceeded |
| 9 |
Runtime error |
301 ms |
60880 KB |
Memory limit exceeded |
| 10 |
Runtime error |
273 ms |
57052 KB |
Memory limit exceeded |
