#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
t=0; char ch=getchar(); int f=1;
while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const ll INF=1e18;
const int maxm=(1e7)+10;
const int maxn=(2e5)+10;
int n,fa[maxn];
int lsh[maxn],N,H[maxn],C[maxn];
vector<int> son[maxn];
int tot,ls[maxm],rs[maxm];
ll delta[maxn],ans,tr[maxm],mx[maxm],lazy[maxm];
int rt[maxn],row,rub[maxm];
void pushup(int root) {
tr[root]=tr[ls[root]]+tr[rs[root]];
mx[root]=max(mx[ls[root]],mx[rs[root]]);
}
void F(int &root) {
if (!root) {
if (row) root=rub[row],row--;
else root=++tot;
ls[root]=rs[root]=0;
mx[root]=0,lazy[root]=INF;
tr[root]=0;
}
}
void pushdown(int root,int l,int r,int mid) {
if (lazy[root]==INF) return;
F(ls[root]),F(rs[root]);
lazy[ls[root]]=lazy[rs[root]]=mx[ls[root]]=mx[rs[root]]=lazy[root];
tr[ls[root]]=lazy[root]*(mid-l+1);
tr[rs[root]]=lazy[root]*(r-mid);
lazy[root]=INF;
}
int merge(int l,int r,int x,int y) {
if (!x||!y) return x+y;
if (l==r) {
tr[x]+=tr[y]; mx[x]=tr[x];
rub[++row]=y;
return x;
}
int mid=(l+r)>>1;
pushdown(x,l,r,mid),pushdown(y,l,r,mid);
ls[x]=merge(l,mid,ls[x],ls[y]);
rs[x]=merge(mid+1,r,rs[x],rs[y]);
rub[++row]=y;
pushup(x);
return x;
}
ll query(int x,int l,int r,int &root) {
if (l==r) return tr[root];
int mid=(l+r)>>1; pushdown(root,l,r,mid);
if (x<=mid) return query(x,l,mid,ls[root]);
return query(x,mid+1,r,rs[root]);
}
void change(int L,int R,int l,int r,int &root,ll delta) {
F(root);
//if (l>r) assert(0);
if (L<=l&&r<=R) {
tr[root]=delta*(r-l+1);
lazy[root]=mx[root]=delta;
return;
}
int mid=(l+r)>>1; pushdown(root,l,r,mid);
if (L<=mid) change(L,R,l,mid,ls[root],delta);
if (mid<R) change(L,R,mid+1,r,rs[root],delta);
pushup(root);
}
int find(int x,int l,int r,int root,ll delta) {
//printf("%d %d\n",l,r);
//if (l>r) exit(0);
if (l==r) return l;
int mid=(l+r)>>1; pushdown(root,l,r,mid);
if (x<=mid) return find(x,l,mid,ls[root],delta);
if (mx[ls[root]]>delta) return find(mid,l,mid,ls[root],delta);
return find(x,mid+1,r,rs[root],delta);
}
void dfs(int u) {
delta[u]=C[u];
change(H[u],H[u],1,N,rt[u],-C[u]);
//printf("u1=%d : ",u);
//for (int i=1;i<=N;i++) printf("%lld ",query(i,1,N,rt[u])+delta[u]); puts("");
//for (int i=1;i<=N;i++) if (i!=H[u]) dp[u][i]+=C[u];
printf("? %d\n",u);
for (int v : son[u]) {
dfs(v);
delta[u]+=delta[v];
//printf("mergein %d %d\n",u,v);
rt[u]=merge(1,N,rt[u],rt[v]);
//printf("mergeout %d %d\n",u,v);
/*for (int i=1;i<=N;i++) {
dp[u][i]+=dp[v][i];
}*/
}
ll x=query(H[u],1,N,rt[u]);
int pos=find(H[u],1,N,rt[u],x);
//printf("pos=%d\n",pos);
change(pos,H[u],1,N,rt[u],x);
// for (int i=1;i<=H[u];i++) dp[u][i]=min(dp[u][i],dp[u][H[u]]);
// printf("u=%d : ",u);
// for (int i=1;i<=N;i++) printf("%lld ",query(i,1,N,rt[u])+delta[u]); puts("");
}
int main() {
//freopen("1.txt","r",stdin);
read(n);
for (int i=1;i<=n;i++) {
read(fa[i]),read(H[i]),read(C[i]);
if (i!=1) son[fa[i]].push_back(i);
lsh[++N]=H[i];
}
sort(lsh+1,lsh+N+1); N=unique(lsh+1,lsh+N+1)-lsh-1;
for (int i=1;i<=n;i++) H[i]=lower_bound(lsh+1,lsh+N+1,H[i])-lsh;
//for (int i=1;i<=n;i++) printf("%d ",H[i]); puts("");
dfs(1);
ans=INF;
for (int i=1;i<=N;i++) ans=min(ans,query(i,1,N,rt[1])+delta[1]);
printf("%lld\n",ans);
printf("%d\n",tot);
return 0;
}
/*
0. Enough array size? Enough array size? Enough array size? Integer overflow?
1. Think TWICE, Code ONCE!
Are there any counterexamples to your algo?
2. Be careful about the BOUNDARIES!
N=1? P=1? Something about 0?
3. Do not make STUPID MISTAKES!
Time complexity? Memory usage? Precision error?
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
506 ms |
8172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
