lp3605 USACO Promotion Counting晋升者计数

题意是求树上逆序对。
统计方式基本和序列逆序对相同。但是需要注意的是,由于树上逆序对需要求的是,一个节点的「子孙节点」中权值比它大的个数,故而可以求差:
具体地来说,在每一次搜索到一个节点之前,把已有的比它大的个数先记录下来,然后往下搜索。在搜索完毕之后将比它大的个数的结果减去原有的比它大的数量,这就是答案。
很容易可以知道这个增量一定是在搜索它的子孙节点的时候增加的。
记住填写的变量到底是\(X\)还是\(b_{X}\).

发表评论

您的电子邮箱地址不会被公开。