1 条题解
-
0

#include <cstdio> #include <iostream> using namespace std; const int M = 100005; const int N = 100*M; #define ll long long int read() { int x=0,f=1;char c; while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;} while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } int n,m,k,tot,f[M],d[M],w[M],rt[M]; int cnt,ls[N],rs[N];ll mi[N],ad[N],mx[N]; struct edge { int v,next; }e[M]; int same(int x) { return !ls[x] && !rs[x]; } void add(int x,ll y) { if(!x) return ; mi[x]+=y;mx[x]+=y;ad[x]+=y; } void up(int x) { mx[x]=max(mx[ls[x]],mx[rs[x]]); mi[x]=min(mi[ls[x]],mi[rs[x]]); if(mx[x]==mi[x]) ls[x]=rs[x]=0;//delete } void down(int x) { if(ad[x]) { add(ls[x],ad[x]); add(rs[x],ad[x]); ad[x]=0; } } int merge(int x,int y) { if(!x || !y) return x+y; if(same(y)) { add(x,mx[y]); return x; } if(same(x)) { add(y,mx[x]); return y; } down(x);down(y); ls[x]=merge(ls[x],ls[y]); rs[x]=merge(rs[x],rs[y]); up(x); return x; } ll ask(int x,int l,int r,int p) { if(same(x)) return mx[x]; int mid=(l+r)>>1;down(x); if(mid>=p) return ask(ls[x],l,mid,p); return ask(rs[x],mid+1,r,p); } void upd(int &x,int l,int r,int L,int R,ll v) { if(l>R || L>r || mi[x]>=v) return ; if(mx[x]<=v && L<=l && r<=R) { mx[x]=mi[x]=v; ls[x]=rs[x]=ad[x]=0; return ; } int mid=(l+r)>>1;down(x); if(same(x)) { ls[x]=++cnt;rs[x]=++cnt; mx[ls[x]]=mi[ls[x]]=mx[rs[x]]=mi[rs[x]]=mx[x]; } upd(ls[x],l,mid,L,R,v); upd(rs[x],mid+1,r,L,R,v); up(x); } void dfs(int u) { rt[u]=++cnt; for(int i=f[u];i;i=e[i].next) { int v=e[i].v; dfs(v); rt[u]=merge(rt[u],rt[v]); } if(d[u]) upd(rt[u],1,k,d[u],k,w[u]+ask(rt[u],1,k,d[u])); } signed main() { n=read();m=read();k=read(); for(int u=2;u<=n;u++) { int v=read(); e[++tot]=edge{u,f[v]},f[v]=tot; } for(int i=1;i<=m;i++) { int v=read(); d[v]=read();w[v]=read(); } dfs(1); printf("%lld\n",mx[rt[1]]); }
- 1
信息
- ID
- 2419
- 时间
- 2000ms
- 内存
- 1024MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者