。。。
这一题本来是个简单题
正常比赛不应该出到标程的1.5倍时限吗
std也是卡着过的。。

[doc的题解] 本题是彻头彻尾的树形动态规划, 非常简单, 是本次比赛中最简单的一题.
我们需要维护 f[0][x] f[1][x] g[0][x] g[1][x] 分别表示对于以x为根的树 (哦这里先需要把问题变成有根数, 随便选取一个根就好了), 如果在x没有匹配掉的情况下, 最多能有f[0][x]对匹配, 方案有g[0][x]组, 如果在x已经匹配了的情况下(当然是指和x子树中的点匹配, 也就是x的某一个子节点), 最多能有f[1][x]对匹配, 方案有g[1][x]组.
问题的转移需要考虑 x 是与哪一个子节点匹配的 (比如说与y匹配), 那么就可以利用 f[0][y] 与 f[0][z] f[1]z 来得到x的状态.
整体十件复杂度是O(n)的.
一些可以避免超时的方法包括:
(1) 对于读入进行优化, 对于c/c++选手可以利用getchar()读入数据, 这样比一般直接读入整数要快.
(2) 本题如果写递归是有可能RE的. 但是写非递归常数太大也会TLE.
(3) 可以考虑直接汇编申请栈空间, 对于c/c++选手可以用下面的方法.
int size = 8 << 20;
char p = (char)malloc(size) + size;
asm("movl %0, %%esp\n" :: "r"(p));
来获得更大的栈空间, 然后直接递归写就ok了. 标称只有不足70行, 应该是很简单的.
(4) 当然vj的评测极们速度各不相同, 有的时候还要看评测机的心情, 所以如果依然也是有可能的.

略显霸气吧

我知道怎么提前发题解啊