嗯，虽然没有评测插件，但是我能找到的所有标程都能通过……所以大胆的写吧……

f[i][j]表示i为根节点，有j个子节点时的最大盈利注意会取到负数！。
Profit[i]表示i节点的利润。
ChildNum[i]表示以i为根节点的叶子节点的个数。
child[i]保存i的子节点。
Dp:
枚举子节点：f[x][i]=Max(f[x][i],f[tmpNum][j]+f[x][i-j]-tmpCost);
如果x到了叶子节点:f[x][1]=Profit[x]; ChildNum[x]=1;

曾经我以为这道题好难。。。

感觉自己弱爆了。。。各种出错，无奈了。。

在SPOJ上要求输出方案，在最小化费用和同时最小化标号和……然后因为没看到这一句跪了一天……

一直不理解递推，表示从前往后计算真的很弱。。

回复 @cstdio :
谢！

'strlen' was not declared in this scope是闹哪样？我用#include <string>不行，用#include <cstring>就可以？

第一次提交还以为内存要爆呢==

看错题wa两次。。。。。。

Floyd.....

真的是kmp模板题！！！！

谁知道string也能比较大小！

可以用DP做。
将点按照X为第一关键字，Y为第二关键字排序
F[i][j]表示1—j个点中加i个矩形面积的最小值
s[i][j]表示覆盖i-j矩形的面积
f[i][j]=max{f[i-1][k]+s[k+1][n]}
但是最后一个点过不去不知道为什么

所以一开始看错题解了。。。。。。 (╯‘□′)╯（┻━┻

KMP模版题（我这个是未改进next函数的KMP，即MP算法，在<训练指南>里有提到）

行，这题目还好

回复 @cstdio :
我是蒟蒻，怎么可能觉得水，我是觉得斯坦纳树太神了不会做，发现可以卡常数过去（明显就是乱搞）
不乱搞题是因为最近好像得了手残+脑残光环，交题10次（10次是少的）内定不过，现在攒题攒了好几道

第一次用long long double 提交居然提示错误