洛谷：P2015 二叉苹果树（dp树，普及/提高-）

题目：

分析：看错题目，要删几个！。。。减一下就欧克啦。但是，减去一个不单单是减去了一个啊。是减去了一串啊！

代码：

#include<bits/stdc++.h>
using namespace std;
int m,n;
int A[101][2];//存放子树。
vector<vector<int> >vv; 
int B[101][101];//存放树上的苹果
long long D[101][101];
int t[101];//存放个数。
map<int,int> mm;
long long f(int x,int y)
{if(D[x][y]!=-1) return D[x][y];//特殊。if(y==0){//统计 if(A[x][0]==-1) return 0;D[x][y]=B[x][A[x][0]]+f(A[x][0],y)+B[x][A[x][1]]+f(A[x][1],y);return D[x][y];}if(A[x][0]==-1||t[x]<y) return -(1<<30);if(t[x]==y) return 0;D[x][y]=0;//都不long long a=-1;for(int i=0;i<=y;i++) a=max(a,B[x][A[x][1]]+B[x][A[x][0]]+f(A[x][0],i)+f(A[x][1],y-i));//左右long long b=-1; if(y>=1+t[A[x][0]])b=B[x][A[x][1]]+f(A[x][1],y-1-t[A[x][0]]);if(y>=1+t[A[x][1]])b=max(b,B[x][A[x][0]]+f(A[x][0],y-1-t[A[x][1]]));D[x][y]=max(a,b);if(D[x][y]<0) D[x][y]=-(1<<30);return D[x][y];
}
void f2(int x)
{mm[x]=1;for(int i=0;i<vv[x].size();i++){if(mm[vv[x][i]]==0) {if(A[x][0]==-1){A[x][0]=vv[x][i];}else{A[x][1]=vv[x][i];}f2(vv[x][i]);} }
}
int f3(int x)
{if(t[x]!=0) return t[x];if(A[x][0]==-1) {t[x]=0;return 0;}t[x]=2+f3(A[x][1])+f3(A[x][0]);return t[x];
} 
int main()
{cin>>m>>n;memset(D,-1,sizeof(D));memset(A,-1,sizeof(A));memset(t,0,sizeof(t));vector<int> v;for(int i=0;i<=m;i++) vv.push_back(v);for(int i=1;i<m;i++){int a,b,c;cin>>a>>b>>c;B[a][b]=B[b][a]=c;vv[a].push_back(b);vv[b].push_back(a);}f2(1);f3(1);//long long c=0;cout<<f(1,m-1-n);
}