HBC235690[SDOI2013]费用流,二分,网络流,分治孤独的树题解

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

给出一棵nnn个点n1n-1n1条边的树，树的节点为1n1 sim n1n，节点iii具有权值val[i]val[i]val[i]，每次操作选择一个节点iii，再选择val[i]val[i]val[i]的一个质因子xxx，然后令val[i]=val[i]÷xval[i] = val[i] div xval[i]=val[i]÷x，问：最少操作几次，才能让这棵树变成一棵孤独的树， 孤独的树的定义：不存在一条边连接的两个节点uvu vuv，gcd>1gcd>1gcd>1。

给出一棵 nnn 个点 n−1n-1n−1 条边的树。树的节点为 1∼n1 sim n1∼n，节点 iii 具有权值 val[i]val[i]val[i]。每次操作选择一个节点 iii，再选择 val[i]val[i]val[i] 的一个质因子 xxx，然后令 val[i]=val[i]÷xval[i] = val[i] div xval[i]=val[i]÷x。问：最少操作几次，才能让这棵树变成一棵孤独的树。 孤独的树的定义：不存在一条边连接的两个节点 u vu vu v，gcd(val[u],val[v])>1gcd(val[u],val[v])>1gcd(val[u],val[v])>1。

成为编程大师，不再是梦想！全网最全C++题库，助您开启编程新篇章。

标签： HBC235690[SDOI2013]费用流 二分 网络流 分治孤独的树题解