牛客最长树链
给出一颗树,每个结点都有一个权值,求出最长的一条链满足该链上所有点的最大公因数大于1。
和队友讨论了一下,队友给出了暴力建图跑树的直径思路,我感觉会tle,不过经过好几轮hack和反hack,慢慢摸索出了一种正解。
因为所要找的链的最大公因数要大于1,也就是这条链上所有结点都要有一个相同的质因子。
按照结点权值的质因子对所有结点进行分类,分类后按照质因子进行建图,对每个新建的图跑一次树的直径就是一条最长链。
例如样例,总共有$2、3、5$三个质因子,第一次考虑质因子$2$的时候,我们选择有质因子$2$的点进行建树。剩下结点$1、 2、 4$,对这三个点都跑一次树的直径(因为这个图不一定是一颗完整的树,可能是多个不连通的树。当然,我们也不必所有点跑一遍,这样必然会tle,我们可以对跑过的连通块进行标记)每次取max。
上面提到的选点的操作,事实上,我们可以将原来的树用一个vis数组标记,只有被标记的点才是我们选择的点。
$tips:$对于用于标记的数组,如果初始化操作要做很多次,我们可以用$vis[i]=ct$ 标记 ,用$vis[i]==ct$ 判断,每一轮$ct++$,这样会快很多
AC代码:
1 | int a[maxn], vis[maxn], vis2[maxn]; |