题目描述

几乎整个Byteland王国都被森林和河流所覆盖。小点的河汇聚到一起，形成了稍大点的河。就这样，所有的河水都汇聚并流进了一条大河，最后这条大河流进了大海。这条大河的入海口处有一个村庄——名叫Bytetown。

在Byteland国，有n个伐木的村庄，这些村庄都座落在河边。目前在Bytetown，有一个巨大的伐木场，它处理着全国砍下的所有木料。木料被砍下后，顺着河流而被运到Bytetown的伐木场。Byteland的国王决定，为了减少运输木料的费用，再额外地建造k个伐木场。这k个伐木场将被建在其他村庄里。这些伐木场建造后，木料就不用都被送到Bytetown了，它们可以在运输过程中第一个碰到的新伐木场被处理。显然，如果伐木场座落的那个村子就不用再付运送木料的费用了。它们可以直接被本村的伐木场处理。

注：所有的河流都不会分叉，形成一棵树，根结点是Bytetown。

国王的大臣计算出了每个村子每年要产多少木料，你的任务是决定在哪些村子建设伐木场能获得最小的运费。其中运费的计算方法为：每一吨木料每千米1分钱。

输入输出格式

输入格式：

 

第一行包括两个数 n（2≤n≤100），k（1≤k≤50,且 k≤n）。n为村庄数，k为要建的伐木场的数目。除了Bytetown外，每个村子依次被命名为1，2，3……n，Bytetown被命名为0。

接下来n行，每行3个整数：

wi——每年i村子产的木料的块数（0≤wi≤10000）

vi——离i村子下游最近的村子（即i村子的父结点）（0≤vi≤n）

di——vi到i的距离(千米)。（1≤di≤10000）

保证每年所有的木料流到bytetown的运费不超过2,000,000,000分

50％的数据中n不超过20。

 

输出格式：

 

输出最小花费，单位为分。

 

输入输出样例

输入样例#1：

4 21 0 11 1 1010 2 51 2 3

输出样例#1：

4 ps;题面沾了落谷的； 一个不错的树形dp题 由题意来看 这是一颗树 我们可以将节点和可支配伐木场数作为状态，再对每一节点的子节点分配伐木场数即可； 但这样显然是不行的，先不谈时间的问题，单是“对每一节点分配伐木场数”这一要求就难以利用代码实现（焫鷄认为） 所以我们秉承着复杂问题简单化的思想 把他化简为一个左儿子右兄弟的二叉树，这样我们对于每一个节点，只需分配两个子节点即可； 这样提交上去，只能拿到30分，时间大大超时。 那我们就应该考虑一下该如何优化了。 首先对于dp问题我们必须是要用到记忆化搜索的（或是状态转移方程），但是如果单单的记录节点和伐木数这两种状态也是很复杂的，因为对于一个点来说，他拥有的伐木数确定并不意味着这个点是唯一的，因为之前的伐木数分配我们并不清楚，所以我们决定再加上一个状态，即之前的伐木数分配。但其实我们并不需要记录之前所有的分配，只需记录与该点有关的即可，也就是离该点最近的那个伐木场的位置，有了这三个状态，程序的效率就会高上许多，但这个脏题是真的脏，这还是不掉，只能拿到50分。 我们继续思考，为什么会超时，经过思考之后发现，由于程序分配伐木场数是枚举的，所以可能会出现以下情况:     该点之下的点只剩下n个，而可用的伐木场数k>n; 在这种情况下，我们不必继续搜索，直接返回0即可，加上这个优化，就终于能拿到这不容易的AC了

/*jzoj	1306 2017  3  27 ;by century*/#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int dis[100000];int w[100000];int v[100000];int a[1000][1000];int top[10000];int child[1000000];int brother[1000000];int n,k;int f[200][200][200];int ppp[10000];int diss(int x,int dix,int father){	dis[x]=dix;	for(int i=1;i<=n;i++)	{		if(a[x][i]!=-1)		{			if(i!=father)			ppp[x]+=diss(i,dix+a[x][i],x);		}	}	return ppp[x]+1;}int vvv(int x){	if(x==-1)return 0;	ppp[x]=vvv(child[x])+vvv(brother[x]);	return ppp[x]+1;}int dfs(int x,int str,int num,int k){	if(x==-1)return 0;	if(f[x][num][str])return f[x][num][str];	if(num>ppp[x])return 0;	int ans=-1;	//x不选	for(int i=0;i<=num;i++)	{		if(ans==-1||ans>dfs(child[x],str,i,k+1)+dfs(brother[x],str,num-i,k+1))		ans=dfs(child[x],str,i,k+1)+dfs(brother[x],str,num-i,k+1);		}	if(ans==-1)	ans=w[x]*(dis[x]-dis[str]);	else ans+=w[x]*(dis[x]-dis[str]);	if(num>0&&x!=0)//x选	{		int sum=-1;		int kk=num-1;		for(int i=0;i<=kk;i++)		{			if(sum==-1||dfs(child[x],x,i,k+1)+dfs(brother[x],str,kk-i,k+1)
            
             >n>>k; for(int i=1;i<=n;i++) { int vv; cin>>w[i]>>vv>>v[i]; a[i][vv]=v[i]; a[vv][i]=v[i]; brother[i]=child[vv]; child[vv]=i; } diss(0,0,-1); vvv(0); cout<
             
              <