1 条题解

  • 0
    @ 2026-7-4 11:01:59

    #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
    上传者