#include <Seter> - using namespace Orz;

1503: [NOI2004]郁闷的出纳员

RunID	User	Problem	Result	Memory	Time	Language	Code Length	Submit Time
170236	Seter	1503	Accepted	7980 kb	492 ms	C/Edit	2178 B	2011-11-04 07:48:10

这几天在学Splay，果断被虐成傻X……一开始看ZKW的Splay，信心满满写自顶向下的非递归Splay，结果每次写了一半都感觉自己完全看不懂ZKW在干吗，然后全部删掉……

RunID	User	Problem	Result	Memory	Time	Language	Code Length	Submit Time
167895	Seter	1103	Accepted	13108 kb	1632 ms	C/Edit	1387 B	2011-10-31 19:34:58

傻X题……那为什么要写题解呢……庆祝自己又一题RANK1呗……而且这次速度特别快……代码也很短，囧……

其实真正原因是为了纪念爆栈……用PAS的同学直接DFS递归就A掉了这题，我以为C也可以，没想到被坑了！！最后还是写了个栈，4行……唉……郁闷！

小黑书上说朱刘算法求的是不定根最小树形图，但是网上找到的资料都说是定根最小树形图……管他呢……

前前后后写了六个小时左右……一开始写每次消掉一个环的DFS，各种2B错误，调了三个小时才好……

然后又改成BFS+拓扑排序的一次消去所有环的方法……这样可以不用记录最小入边的反向边。然后边减小的量用个数组保存起来，这样就不用记录整张图的反向边了。

坑了个爹的FFT……原理只了解到卷积那一步……怎么转换成整系数而非sincos乱搞的系数那个完全不了解……权当背代码了……

其实代码灰常好写……根本不像我想像的那样超级复杂！代码的关键在于如何选P（[tex]$P=C*2^{\log n}+1$[/tex]）……