Description

0v0在野外看到了一棵Galo树，看到食物的0v0瞪大了眼睛，变成了OvO。 这棵Galo树可以看做是一棵以1号点为根的n个点的有根数，除了根节点以外，每个节点i都有一个Galo，美味度为w[i]。 OvO发现，如果她摘下了i号Galo，那么i的子树中的Galo以及i到根的路径上的其他Galo都会死掉。 OvO的袋子只能装k个Galo，她的嘴巴里还能叼1个，请问她所摘Galo的美味度之和的最大值是多少？

Solution

O(nm2) 的暴力大家应该都会，据说这个加点优化即可跑过 这类问题，先把它映射到dfs序上，在这上面做， 这样，转移就十分显然了，要不直接不选，从上一个转过来，要不自己选，从不是自己子树的第一个转移过来，

复杂度： O(nm)

Code

#include <cstdio> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fod(i,a,b) for(int i=a;i>=b;i--) #define efo(i,q) for(int i=A[q];i;i=B[i][0]) #define min(q,w) ((q)>(w)?(w):(q)) #define max(q,w) ((q)<(w)?(w):(q)) #define W(i,j) ((i)*m-m+(j)) using namespace std; typedef long long LL; const int N=100500; int read(int &n) { char ch=' ';int q=0,w=1; for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar()); if(ch=='-')w=-1,ch=getchar(); for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n; } int m,n; int b[N],Si[N]; int d[N]; int B[2*N][2],A[N],B0; LL f[10200000]; LL ans; void link(int q,int w){B[++B0][0]=A[q];A[q]=B0,B[B0][1]=w;} int dfs(int q) { d[++d[0]]=q;Si[q]=1; efo(i,q)Si[q]+=dfs(B[i][1]); return Si[q]; } int main() { int q,w; read(n),read(m);m=min(n,m+1); fo(i,2,n)read(q),read(b[i]),link(q,i); dfs(1); fod(i,n,1) { int t=W(i,1); fo(j,1,m) { f[t]=max(f[t+m],(j>1?f[W(i+Si[d[i]],j-1)]:0)+(LL)b[d[i]]); t++; } } ans=0; fo(i,1,m)ans=max(ans,f[i]); printf("%lld\n",ans); return 0; }