题面链接
sol
这是一篇%这位聚聚的毫无意义的题解。
就是背包，拆点的套路值得学习。
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gt getchar()
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
inline int in()
{
int k=0;char ch=gt;
while(ch<'-')ch=gt;
while(ch>'-')k=k*10+ch-'0',ch=gt;
return k;
}
const int N=4e4+5,K=5e5+5,NK=6e7+5;
using std::vector;
inline void clear(vector<int>&now){vector<int>emp;std::swap(emp,now);}
vector<int>G[N];int w[N],a[N],n,res,cnt,k,fa[N],q1[K<<1],q2[K<<1],h;
int dfn1[N],dfn2[N],df1,df2,siz[N],line[N],is[N],pos1[N],pos2[N],he,ta;
int dp1[NK],dp2[NK];
inline void init()
{
for(int i=0;i<=cnt;++i)clear(G[i]),is[i]=line[i]=siz[i]=0;
for(int i=0;i<=(cnt+1)*(k+1);++i)dp1[i]=dp2[i]=0;
df1=df2=res=cnt=h=0;
}
inline void DP(int *dfn,int *dp)
{
for(int i=1;i<=cnt;++i)
{
int v=dfn[i];he=ta=1;q1[ta]=q2[ta]=0;
for(int j=1;j<=k;++j)
{
he+=q1[he]<j-a[v];int val=dp[(i-1)*(k+1)+j]-j*w[v];
dp[i*(k+1)+j]=std::max(q2[he]+j*w[v],dp[(i-siz[v])*(k+1)+j]);
while(he<=ta&&q2[ta]<=val)--ta;q1[++ta]=j,q2[ta]=val;
}
}
}
#define v G[u][i]
void dfs1(int u)
{
siz[u]=1;int sz=G[u].size();
for(int i=0;i<sz;++i)
dfs1(v),siz[u]+=siz[v];
dfn1[++df1]=u,pos1[u]=df1;
}
void dfs2(int u)
{
int sz=G[u].size();
for(int i=sz-1;~i;--i)
line[v]=line[u]+w[v],dfs2(v);
dfn2[++df2]=u,pos2[u]=df2;
}
#undef v
inline void work()
{
n=in(),k=in();cnt=n;
for(int i=1;i<=n;++i)fa[i]=in(),a[i]=in(),w[i]=in(),is[fa[i]]=1;
for(int i=1;i<=n;++i)
{
G[fa[i]].push_back(i);
if(a[i]>1)a[++cnt]=a[i]-1,a[i]=1,w[cnt]=w[i],G[i].push_back(cnt);
}
line[1]=w[1],dfs1(1),dfs2(1);DP(dfn1,dp1),DP(dfn2,dp2);
for(int i=1;i<=n;++i)
if(!is[i])
{
for(int j=0;j<=k;++j)
res=std::max(res,dp1[(pos1[i]-1)*(k+1)+j]+
line[i]+dp2[(pos2[i]-siz[i])*(k+1)+(k-j)]);
}
printf("%d
",res);
}
int main()
{
int t=in();
while(t--)work(),init();
return 0;
}