이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const long long inf=1e18;
const int maxn=2e5+9;
struct node{
long long val,lazy;
node(){
val=lazy=0;
}
};
node cmp(const node &p,const node &q){
node r;
r.val=max(p.val,q.val);
return r;
}
struct IT{
vector<node>st;
void resz(int n){
st.resize(4*n+9);
}
void push(int id){
if (st[id].lazy){
st[id<<1].val+=st[id].lazy;
st[id<<1|1].val+=st[id].lazy;
st[id<<1].lazy+=st[id].lazy;
st[id<<1|1].lazy+=st[id].lazy;
st[id].lazy=0;
}
}
void update(int id,int l,int r,int u,int v,long long val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
st[id].lazy+=val;
st[id].val+=val;
return;
}
push(id);
int mid=(l+r)>>1;
update(id<<1,l,mid,u,v,val);
update(id<<1|1,mid+1,r,u,v,val);
st[id]=cmp(st[id<<1],st[id<<1|1]);
}
long long get(int id,int l,int r,int u){
if (r<u)return inf;
while (true){
if (l==r)return st[id].val;
push(id);
int mid=(l+r)>>1;
if (mid>=u){
id=(id<<1);
r=mid;
}
else {
id=(id<<1|1);
l=mid+1;
}
}
return 0;
}
int walk(int id,int l,int r,long long val){
if (st[id].val<val)return -1;
if (l==r)return l;
int mid=(l+r)>>1;
push(id);
if (st[id<<1].val>=val)return walk(id<<1,l,mid,val);
else return walk(id<<1|1,mid+1,r,val);
}
};
vector<int>a[maxn];
int h[maxn];
long long c[maxn];
int par[maxn];
struct type{
int l,r;
long long val;
};
vector<type>b[maxn];
int sub[maxn];
vector<int>vertice[maxn];
void predfs(int u){
sub[u]=sz(vertice[u]);
for (auto &v:a[u]){
predfs(v);
sub[u]+=sub[v];
if (sub[v]>sub[a[u][0]])swap(a[u][0],v);
}
}
int n,m;
IT st;
int deg[maxn];
long long sum[maxn];
void dfs(int u){
if (!a[u].empty()){
for (auto v:a[u]){
if (v==a[u][0])continue;
dfs(v);
int pointer=m;
while (pointer){
type tmp;
tmp.val=st.get(1,1,m,pointer);
tmp.r=pointer;
tmp.l=st.walk(1,1,m,tmp.val);
b[v].pb(tmp);
pointer=tmp.l-1;
}
for (auto x:b[v]){
st.update(1,1,m,x.l,x.r,-x.val);
}
}
dfs(a[u][0]);
for (auto v:a[u]){
if (v==a[u][0])continue;
for (auto x:b[v]){
st.update(1,1,m,x.l,x.r,x.val);
}
vector<type>().swap(b[v]);
}
}
vector<int>xd;
long long ss=0;
for (auto v:vertice[u]){
sum[h[v]]+=c[v];
ss+=c[v];
xd.pb(h[v]);
}
xd.pb(0);
sort(all(xd));
xd.resize(distance(xd.begin(),unique(all(xd))));
for (auto v:xd)sum[v]=ss-sum[v];
st.update(1,1,m,xd.back()+1,m,ss);
for2(i,sz(xd)-1,1){
long long hjhj=st.get(1,1,m,xd[i]+1);
long long val=st.get(1,1,m,xd[i]);
if (hjhj<val+sum[xd[i]]){
st.update(1,1,m,xd[i],xd[i],-val+hjhj);
val=hjhj;
}
else {
val+=sum[xd[i]];
st.update(1,1,m,xd[i],xd[i],sum[xd[i]]);
}
int l=xd[i-1]+1,r=xd[i]-1;
while (l<=r){
long long vl=st.get(1,1,m,r);
if (vl+ss<=val)break;
int pos=st.walk(1,1,m,vl);
if (pos<l)pos=l;
st.update(1,1,m,pos,r,-vl+val);
r=pos-1;
}
st.update(1,1,m,l,r,ss);
}
for (auto v:xd)sum[v]=0;
}
bool vis[maxn];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("temp.INP","r",stdin);
//freopen("temp.OUT","w",stdout);
cin>>n;
vector<int>nn;
nn.pb(1);
for1(i,1,n){
int p;
cin>>p;
par[i]=p;
cin>>h[i]>>c[i];
nn.pb(h[i]);
}
sort(all(nn));
nn.resize(distance(nn.begin(),unique(all(nn))));
m=sz(nn);
map<int,int>nenso;
for1(i,0,sz(nn)-1){
nenso[nn[i]]=i+1;
}
for1(i,1,n)h[i]=nenso[h[i]];
h[0]=1;
st.resz(m);
for1(i,1,n){
deg[par[i]]++;
}
queue<int>dag;
for1(i,1,n)if (!deg[i])dag.push(i);
while (!dag.empty()){
auto u=dag.front();
dag.pop();
deg[par[u]]--;
if (!deg[par[u]])dag.push(par[u]);
}
for1(i,1,n)if (par[i]!=i&&!deg[i])a[par[i]].pb(i);
for1(i,1,n)vertice[i].pb(i);
for1(i,1,n){
if (vis[i]||!deg[i])continue;
int u=i;
vector<int>xd;
while (true){
if (vis[u])break;
xd.pb(u);
vis[u]=1;
u=par[u];
}
u=xd.back();
a[0].pb(u);
xd.pop_back();
for (auto v:xd){
vertice[u].pb(v);
vertice[v].clear();
for (auto x:a[v]){
a[u].pb(x);
}
vector<int>().swap(a[v]);
}
}
predfs(0);
dfs(0);
cout<<st.get(1,1,m,1);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |