#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define int i64
#define FP_EPS 1e-11
#define COUT_FP 11
// #define CPP20 1
#define pushb push_back
#define pushf push_front
#define popb pop_back
#define popf pop_front
#define empl emplace
#define emplb emplace_back
#define emplf emplace_front
#define fi first
#define se second
#define mkp make_pair
#define mkt make_tuple
#define cxp constexpr
#define lb lower_bound
#define ub upper_bound
#define reduce accumulate
#define itos to_string
using i64=long long;using u64=unsigned long long;using f64=double;
using pint=pair<int,int>;using tint=tuple<int,int,int>;
template<class T>using Str=basic_string<T>;
//Handy Funcs
template<class T>int sz(const T& x){return x.size();}
template<class T>cxp T inf(){return numeric_limits<T>::max()/2;}
int divc(int a,int b){if(b<0)a=-a,b=-b;return (a>0)?(a+b-1)/b:a/b;}
int divf(int a,int b){if(b<0)a=-a,b=-b;return (a>0)?a/b:(a-b+1)/b;}
cxp int lg2f(int x){return 63-__builtin_clzll(x);}
cxp int lg2c(int x){return 64-__builtin_clzll(x-1);}
template<class T>inline T sq(T x){return x*x;}
bool assmin(auto& a,auto&& b){return a>b?a=b,true:false;}
bool assmax(auto& a,auto&& b){return a<b?a=b,true:false;}
int argmin(const auto& a){return min_element(a.begin(),a.end())-a.begin();}
int argmax(const auto& a){return max_element(a.begin(),a.end())-a.begin();}
void WARN(bool cond,const char* str){
#if DEBUG
static set<const char*> z;
if(cond&&!z.count(str))z.insert(str),cerr<<"[WARN] "<<str<<endl;
#endif
}
template<class T, class P=
#if CPP20
conditional_t<is_same<bool,T>::value,deque<T>,vector<T>>>
#else
vector<T>>
#endif
struct Arr:public P{
Arr():Arr(0){}
explicit Arr(signed n,T init=T()):P(n,init){}
Arr(initializer_list<T>il):P(il){}
#ifdef CPP20
Arr(auto its, auto ite):P(its,ite){}
#endif
T& operator[](signed i){
WARN(i<0,"Negative Index Found");
return P::operator[](i>=0?i:i+this->size());
}
const T& operator[](signed i)const{return P::operator[](i>=0?i:i+this->size());}
T& at(signed i){return *this[i];}
const T& at(signed i)const{return *this[i];}
};
template<class... A> auto ARR(auto n,A&&... a)
{if constexpr(!sizeof...(a)) return n; else return Arr(n,ARR(a...));}
//Monoid
#ifdef CPP20
template<class T, auto _f=[](T x,T y){return x+y;}, T _id=0>
struct Monoid{static cxp auto f=_f,id=_id;};
template<class T, class M=Monoid<T>>
Arr<T> cumf(const Arr<T>& a){
Arr<T> b(sz(a)+1,M::id);
for(int i=0;i<sz(a);i++)
b[i]=M::f(b[i-1],a[i]);
return b;
}
#endif
//Func Exts
#define RETT(...) __VA_ARGS__
#define func(RetT,fname,...) function<RetT(__VA_ARGS__)> fname=[&](__VA_ARGS__)->RetT
#define lam(expr,...) [&](__VA_ARGS__){return expr;}
#define PQ std::priority_queue
template<class T>using PQMax=PQ<T>;
template<class T>using PQMin=PQ<T,vector<T>,greater<T>>;
//Consts
const f64 pi=acosl(-1),eps=FP_EPS;
const int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
//Pre-runs
#if !(DEBUG)
auto __PR1=(ios::sync_with_stdio(0),cin.tie(0),cout.tie(0));
#endif
auto& __PR2=(cout<<fixed<<setprecision(COUT_FP));
//
#define FASTIO
//INPUT
struct FastCIN{
static const int SZ=1<<24;
unsigned cnt=0;char a[SZ+1],*p;
FastCIN(){preload();}
void tie(int x){}
int preload(){return cnt=cin.read(p=a,SZ).gcount();}
inline char pop(){if(!cnt)preload(); return cnt>0?cnt--,*p++:0;}
inline char get(){if(!cnt)preload(); return cnt>0?*p:0;}
void ignore_wsc(){while(get()==' '||get()=='\n')pop();}
operator bool(){return get();}
template<class T>FastCIN& operator>>(T& n){ignore_wsc();n=0;char neg=false;if(get()=='-')neg=true,pop();while('0'<=get()&&get()<='9')n=n*10+pop()-'0';if(neg)n*=-1;return *this;}//int,i64,Mod<mod>
FastCIN& operator>>(char& c){ignore_wsc();c=pop();return *this;}
FastCIN& operator>>(string& s){ignore_wsc();s.clear();while(get()!=' '&&get()!='\n'&&get())s.pushb(pop());return *this;}
FastCIN& operator>>(f64& n){ignore_wsc();string s;while(('0'<=get()&&get()<='9')||get()=='.'||get()=='-')s.pushb(pop());n=stod(s);return *this;}
template<class T> FastCIN& operator>>(Arr<T>& a){for(auto& i:a)*this>>i;return *this;}
template<class T,class U> FastCIN& operator>>(pair<T,U>& a){*this>>a.fi>>a.se;return *this;}
};
struct TokCIN:public FastCIN{
static TokCIN* x;
static TokCIN* instance(){return !x?x=new TokCIN():x;}
template<class T=i64>T tok(){T x;operator>>(x);return x;}
template<class T=i64>Arr<T> toks(int n){Arr<T> a(n);for(auto& i:a)operator>>(i);return a;}
template<class... A> void _read(A&...a){((operator>>(a)),...);}
};
TokCIN* TokCIN::x;
#define cin (*TokCIN::instance())
#define READ(T,...) T __VA_ARGS__;cin._read(__VA_ARGS__);
//OUTPUT
template<class T> ostream& operator<<(ostream& s,const Arr<T>& a){for(auto i:a)cout<<i<<' ';return s;}
template<class T> ostream& operator<<(ostream& o,const pair<T,T>& x){return o<<x.fi<<' '<<x.se;}
template<class... A> void PRINT(A...a){((cout<<a<<' '),...,(cout<<endl));}
//
//NOTE: f(x)=min{f(x+i),i<a}+|x-k|+m -> pf(k)sf(k)ab(-a,m)
//NOTE: sf_inc에 답구하는게 들어있어서, 반드시 한 연산에 대해 pf_dec->sf_inc순서로 호출
struct LeftHull{
void pf_dec(int x){pq.empl(x-bias);}//x이하의 기울기들 -1
int sf_inc(int x){//x이상의 기울기들 +1, pop된 원소 반환(Right Hull관리에 사용됨)
if(pq.empty() or argmin()<=x)return x;
ans+=argmin()-x;//이 경우 최솟값이 증가함
pq.empl(x-bias);//x 이하 -1
int r=argmin();pq.pop();//전체 +1
return r;
}
void add_bias(int x,int y){bias+=x;ans+=y;}//그래프 x축 평행이동
int minval(){return ans;}//최소값
int argmin(){return pq.empty()?-inf<int>():pq.top()+bias;}//최소값 x좌표
void operator+=(LeftHull& a){
ans+=a.ans;
// PQMax<int> tmp=a.pq;
while(sz(a.pq))pf_dec(a.argmin()), a.pq.pop();
// swap(a.pq,tmp);
}
int size()const{return sz(pq);}
// private:
PQMax<int> pq;
int ans=0,bias=0;
};
//NOTE: f(x)=min{f(x+i),a<i<b}+|x-k|+m -> pf(k)sf(k)ab(-a,b,m)
struct SlopeTrick{
void pf_dec(int x){l.pf_dec(-r.sf_inc(-x));}
void sf_inc(int x){r.pf_dec(-l.sf_inc(x));}
void add_bias(int lx,int rx,int y){l.add_bias(lx,0),r.add_bias(-rx,0),ans+=y;}
int minval(){return ans+l.minval()+r.minval();}
pint argmin(){return {l.argmin(),-r.argmin()};}
void operator+=(SlopeTrick& a){l+=a.l,r+=a.r,ans+=a.ans;}
int size()const{return l.size()+r.size();}
// private:
LeftHull l,r;
int ans=0;
};
//LeftHull 역추적 방법: 스텝i의 argmin값을 am(i)라고 하자. 스텝n부터 스텝1까지 ans[i]=min(ans[i+1],am(i))하면 된다. 아래는 증명..은 아니고 간략한 이유
//am(i)<=ans[i+1]일때: ans[i]=am(i)
//x[i]>ans[i+1]일때: ans[i]=ans[i+1] 왜냐하면 f(i,a)는 a<x[i]에서 감소함수이므로 가능한 최대로 오른쪽으로 붙은 ans[i+1]이 최적.
//스텝i에서 add_bias(k,0)한다면 간격제한k가 있는것이므로 ans[i]=min(ans[i+1]-k,x[i])으로 수정.
//LR Hull 역추적은 케이스나눠서 위 방법을 확장하면 될듯
// Random
mt19937 _rng(i64(new int) ^ time(0));
int rd() {
static uniform_int_distribution<int> dist(0, inf<int>());
return dist(_rng);
}
int rd(int e) { return rd() % e; }
int rd(int s, int e) { return rd() % (e - s) + s; }
f64 rdf() {
static uniform_real_distribution<f64> dist(0, 1);
return dist(_rng);
}
void shuffle(auto is, auto ie) { shuffle(is, ie, _rng); }
#define endl '\n'
signed main(){
READ(int,n,m);
// int n=200000,m=100000;
Arr<int> p(n+m),c(n+m);
for(int i=1;i<n;i++){
cin>>p[i]>>c[i];
p[i]--;
// p[i]=rd(i);
// c[i]=rd(10'0000'0000)+1;
}
Arr<SlopeTrick> dp(n+m);
for(int i=n;i<n+m;i++){
cin>>p[i]>>c[i];
p[i]--;
// p[i]=rd(n);
// c[i]=rd(10'0000'0000)+1;
dp[i].pf_dec(c[i]);
dp[i].sf_inc(c[i]);
dp[p[i]]+=dp[i];
}
for(int i=n-1;i;i--){
// dp[i].add_bias(0,0,c[i]);z
if(dp[i].size()==0)continue;
auto [lx,rx]=dp[i].argmin();
dp[i].l.pq.pop();
dp[i].r.pq=PQMax<int>();
dp[i].pf_dec(lx+c[i]);
dp[i].sf_inc(rx+c[i]);
dp[p[i]]+=dp[i];
}
cout<<dp[0].minval()<<endl;
}
Compilation message
fireworks.cpp:38:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
38 | bool assmin(auto& a,auto&& b){return a>b?a=b,true:false;}
| ^~~~
fireworks.cpp:38:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
38 | bool assmin(auto& a,auto&& b){return a>b?a=b,true:false;}
| ^~~~
fireworks.cpp:39:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
39 | bool assmax(auto& a,auto&& b){return a<b?a=b,true:false;}
| ^~~~
fireworks.cpp:39:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
39 | bool assmax(auto& a,auto&& b){return a<b?a=b,true:false;}
| ^~~~
fireworks.cpp:40:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
40 | int argmin(const auto& a){return min_element(a.begin(),a.end())-a.begin();}
| ^~~~
fireworks.cpp:41:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
41 | int argmax(const auto& a){return max_element(a.begin(),a.end())-a.begin();}
| ^~~~
fireworks.cpp:71:31: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
71 | template<class... A> auto ARR(auto n,A&&... a)
| ^~~~
fireworks.cpp:206:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
206 | void shuffle(auto is, auto ie) { shuffle(is, ie, _rng); }
| ^~~~
fireworks.cpp:206:23: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
206 | void shuffle(auto is, auto ie) { shuffle(is, ie, _rng); }
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
