本文从WordPress迁移而来, 查看全部WordPress迁移文章
【UVA提交失败,无法评判】
LCA + 树状数组(线段树)
题意:给出一棵无根树,每个点有颜色,颜色种类只有10种,从1到10标号。有两种操作,一种是改变某个点的颜色,一种是询问点u到v的路径中,出现的次数最多的颜色(输出次数,不是输出对应的颜色标号)。
这题的巧妙之处是,怎么引入线段树?
这题一个重要的突破口是,颜色10种,这是个可以暴力枚举的特征。可以先考虑询问操作。入股我们定义一个dp值,dp[u][col],表示点u到根的路径上,col这种颜色出现了几次。那么就可以跟LCA联系起来。对于询问(u,v)可以先找到LCA,然后枚举每一种颜色,看看u到v的路径上,这种颜色出现了几次
cnt[col] = dp[u][col] + dp[v][col] - 2*dp[lca][col] + (color[lca] == col)
这个式子是很容易理解的,注意最后,如果lca这个点的颜色就是col,加1,否则加0
上面是计算出了1种颜色,那么对应10颜色,就枚举10次,找到最大的cnt[col],就是答案
所以我们要做的就是能维护这个dp数组。要维护就用到了线段树。
我们在求LCA的时候,要用ST算法,是因为,这样才能得到一个序列,一个区间,这才用上线段树,但是和一般的LCA转RMQ不同,要另外构建一个序列
sample:对于一个树,定1为根
1 | 1 2 |
LCA转RMQ得到的序列为
1 | 1 2 4 2 5 2 1 3 1 , 这个序列用于ST算法求LCA |
另外构建的,这个序列的含义很显然,每个节点首次和末次出现的时候都记录了一次,一共记录了2n个节点。我们设置2个数组记录一些信息,L[u]表示点u首次出现的位置,R[u]表示末次出现的位置。
我们用10个树状数组(或线段树,这里其实树状数组更方便),维护信息,10个树状数组是对应10种颜色。
如果一个节点u变色为col,那么就将L[u]这个位置边为1,R[u]这个位置边为-1,(如果是从一个颜色变为另一个颜色,旧的颜色对应的位置L[u] = R[u] = 0)。
我们可以看一个sample,询问4,5的LCA,那就是2,找到L[4],L[5],L[2]从这些位置开始计算一次前缀和,用4,5的前缀和减去2倍2的前缀和,就是4到5的路径上这个颜色出现了多少次
这题是近期做的比较好的一题,要说清楚有些困难,可以看看代码领悟一下。不过代码不能提交不知道对错,自己测过一些数据是对的
1 |
|