M_sea的博客

M_sea的博客

A Mengbier

题解 CF463E 【Caisa and Tree】

posted on 2019-05-16 10:39:19 | under 题解 |

先考虑没有修改怎么做。

先定义一些东西:

vector<int> divi[N]; //divi[i]为节点i的点权的质因子
pair<int,int> ans[N]; //ans[i]为节点i的答案,第一维为深度,第二维为节点编号
set<pair<int,int> > S[V]; //S[i]维护所有含有质因子i的节点

先求出 divi ,然后一遍 $\mathrm{dfs}$ ,结合 S 即可求出每个节点的 ans

具体的求法是,枚举 divi 里的质因数 $i$ ,然后用 S[i] 中最大值更新答案。

然后记得要把当前节点的质因子丢到 S 里去,最后还要撤回。

考虑带修改怎么搞。注意到修改不超过 $50$ 个,那么直接暴力改就好了。

大概有一点抽象?可以看看代码