#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pr(x) printf("%d\n",x)
#define prl(x) printf("%lld\n",x)
#define yes printf("YES\n")
#define no printf ("NO\n")
#define ll long long
#define ld long double
#define pb push_back
#define f first
#define s second
#define tmp (l+r)/2
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const ld pi=2*acos(0);
const ll mod=1e9+7;
const ld eps=1e-9;
const ll ll_max=4e18;
///const ll mod=998244353;
/// make the equation y=m*x+p+g
/// where g is constant and y==dp[i]
/// dp[i]=query(x)+g;
/// Line l={m,p};
/// insert(node*,l);
/// if you want max
/// dp[i]=-query(x)+g;
/// Line l={-m,-p};
/// insert(node* ,l);
using namespace std;
ll RANG = 0;
ll RANGM = 2e9;
struct Line{
int m;
ll p;
Line(){
m=0;
p=ll_max;
}
}fai;
struct node{
Line line;
node *l;
node *r;
node(Line line2=fai,node *l2=NULL,node *r2=NULL)
{
line=line2;
l=l2;
r=r2;
}
};
ll f(Line l,ll x){
return l.m*x+l.p;
}
node* insert(node *cur,Line line,ll st=RANGM,ll en=RANG)
{
node *ret=new node(cur->line,cur->l,cur->r);
ll m=st+(en-st)/2ll;
bool left = f(line, st) < f(ret->line, st);
bool mid = f(line, m) < f(ret->line, m);
if(mid)
swap(line,ret->line);
if(ret->l==NULL)
ret->l=new node();
if(ret->r==NULL)
ret->r=new node();
if(en - st == 0)
{
return ret;
}
else if(left != mid)
{
node *lef=insert(ret->l,line,st,m);
ret->l=lef;
return ret;
}
else
{
node *right=insert(ret->r,line,m+1,en);
ret->r=right;
return ret;
}
}
ll query(node *cur,ll x,ll st=RANGM,ll en=RANG)
{
if (cur == NULL) return f(fai,x);
ll m = st+(en-st)/2ll;
ll curr = f(cur->line, x);
if(en-st==0) return curr;
if(x<=m) return min(curr, query(cur->l,x, st, m));
else return min(curr, query(cur->r,x, m+1, en));
}
int n;
ll s[100001];
ll v[100001];
vector<pair<int,ll>>vec[100001];
node *root[100001];
ll mem[100001];
void dfs(int city,int par,ll q)
{
if(city!=1)
{
mem[city]=(query(root[par],v[city])+q*v[city])+s[city];
root[city]=root[par];
Line l;
l.m=-q;
l.p=mem[city];
root[city]=insert(root[city],l);
}
for(auto c:vec[city])
{
if(c.f==par)
continue;
dfs(c.f,city,c.s+q);
}
}
int main()
{
sc(n);
for(int i=0;i<n-1;i++)
{
int x,y;
ll c;
sc(x);sc(y);scl(c);
vec[x].pb({y,c});
vec[y].pb({x,c});
}
for(int i=2;i<=n;i++)
{
scl(s[i]);
scl(v[i]);
RANG=max(RANG,v[i]);
RANGM=min(RANGM,v[i]);
}
root[1]=new node();
Line l;
l.m=l.p=0;
root[1]=insert(root[1],l);
dfs(1,0,0);
for(int i=2;i<=n;i++)
printf("%lld ",mem[i]);
}
Compilation message
harbingers.cpp: In function 'int main()':
harbingers.cpp:3:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
3 | #define sc(x) scanf("%d",&x)
| ~~~~~^~~~~~~~~
harbingers.cpp:125:5: note: in expansion of macro 'sc'
125 | sc(n);
| ^~
harbingers.cpp:3:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
3 | #define sc(x) scanf("%d",&x)
| ~~~~~^~~~~~~~~
harbingers.cpp:130:9: note: in expansion of macro 'sc'
130 | sc(x);sc(y);scl(c);
| ^~
harbingers.cpp:3:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
3 | #define sc(x) scanf("%d",&x)
| ~~~~~^~~~~~~~~
harbingers.cpp:130:15: note: in expansion of macro 'sc'
130 | sc(x);sc(y);scl(c);
| ^~
harbingers.cpp:4:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
4 | #define scl(x) scanf("%lld",&x)
| ~~~~~^~~~~~~~~~~
harbingers.cpp:130:21: note: in expansion of macro 'scl'
130 | sc(x);sc(y);scl(c);
| ^~~
harbingers.cpp:4:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
4 | #define scl(x) scanf("%lld",&x)
| ~~~~~^~~~~~~~~~~
harbingers.cpp:136:9: note: in expansion of macro 'scl'
136 | scl(s[i]);
| ^~~
harbingers.cpp:4:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
4 | #define scl(x) scanf("%lld",&x)
| ~~~~~^~~~~~~~~~~
harbingers.cpp:137:9: note: in expansion of macro 'scl'
137 | scl(v[i]);
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3796 KB |
Output is correct |
| 3 |
Runtime error |
97 ms |
60844 KB |
Memory limit exceeded |
| 4 |
Runtime error |
113 ms |
56336 KB |
Memory limit exceeded |
| 5 |
Runtime error |
125 ms |
65536 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
164 ms |
65536 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
98 ms |
43212 KB |
Memory limit exceeded |
| 8 |
Runtime error |
153 ms |
65536 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
137 ms |
65536 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
131 ms |
65536 KB |
Execution killed with signal 9 |
