#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct line
{
ll k,n;
line(){}
line(ll a,ll b){k=a;n=b;}
ll eval(ll x){return (k*x+n);}
friend double intersect(line &a,line &b){return (double(b.n-a.n)/(a.k-b.k));}
friend bool ok(line &a,line &b,line &c){return (intersect(a,b)<intersect(b,c));}
};
const int N=100005;
int n;
array<int,3> v[2*N];
int vstart[N];
int ts[N];
int tv[N];
int depth[N];
line trie[N];
int ver[N]; //version of node i
double lim[N];
int p[N][17];
int tcnt=1;
ll res[N];
int add(int a,line l)
{
int to=(++tcnt);
for(int j=16;j>=0;j--)
{
int y=p[a][j];
int x=p[y][0];
if(x!=0&&y!=0&&!ok(trie[x],trie[y],l)) a=y;
}
if(a!=0&&p[a][0]!=0&&!ok(trie[p[a][0]],trie[a],l)) a=p[a][0];
trie[to]=l;
p[to][0]=a;
for(int j=1;j<17;j++) p[to][j]=p[p[to][j-1]][j-1];
lim[to]=intersect(trie[a],trie[to]);
return to;
}
ll opt(int a,ll x)
{
for(int j=16;j>=0;j--)
{
int u=p[a][j];
if(u!=0&&lim[u]>x) a=u;
}
if(lim[a]>x) a=p[a][0];
return trie[a].eval(x);
}
void dfs(int a,int u)
{
if(a==1)
{
ver[a]=1;
trie[1]=line(0,0);
lim[1]=-1e100;
}
else
{
res[a]=ts[a]+opt(ver[u],tv[a])+ll(depth[a])*tv[a];
ver[a]=add(ver[u],line(-depth[a],res[a]));
}
for(int i=vstart[a];i<2*(n-1)&&v[i][0]==a;i++)
{
int b=v[i][1];
int c=v[i][2];
if(b==u) continue;
depth[b]=depth[a]+c;
dfs(b,a);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=0;i<n-1;i++)
{
int a,b,c;
cin >> a >> b >> c;
v[2*i]={a,b,c};
v[2*i+1]={b,a,c};
}
sort(v,v+2*(n-1));
for(int i=2*(n-1)-1;i>=0;i--) vstart[v[i][0]]=i;
for(int i=2;i<=n;i++) cin >> ts[i] >> tv[i];
dfs(1,0);
for(int i=2;i<=n;i++) cout << res[i] << " \n"[i==n];
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
960 KB |
Output is correct |
3 |
Correct |
49 ms |
10480 KB |
Output is correct |
4 |
Correct |
79 ms |
14900 KB |
Output is correct |
5 |
Correct |
75 ms |
19620 KB |
Output is correct |
6 |
Correct |
108 ms |
23992 KB |
Output is correct |
7 |
Correct |
70 ms |
14316 KB |
Output is correct |
8 |
Correct |
126 ms |
20656 KB |
Output is correct |
9 |
Correct |
140 ms |
21748 KB |
Output is correct |
10 |
Correct |
128 ms |
20812 KB |
Output is correct |