D. Potion Brewing （Codeforces Round #778 (Div. 1 + Div. 2, based on Technocup 2022）

赛后补题. 给你一个n个点带权的树,(因为有n-1条边且连通),然后再给一条边 u , v , x , y u,v,x,y u,v,x,y代表 u 点 权 / v 点 权 = x / y u点权/v点权=x/y u点权/v点权=x/y. 你的任务是给树上的点赋值,使得总的点权和最小且满足边之间的比例关系. 思考:首先考虑树高为2的情况,寻找父子关系.首先,如果父亲节点的值确定了,那么每一个儿子的节点的值也一定确定了. 记 x x x为父亲节点的比例, y y y为儿子节点的比例. v a l x val_x valx​为父亲节点的值 v a l y val_y valy​为儿子的值 不难发现,如果要父亲节点都可以满足其儿子节点是一个整数.对于所有的 y y y,均有: v a l y = ( v a l x ∗ y ) / x val_y=(val_x*y)/x valy​=(valx​∗y)/x,把 y / x y/x y/x化为最简的形式后.不难发现, v a l x % x = = 0 val_x\%x==0 valx​%x==0总是能成立.这也就是说. v a l x = l c m ( x 1 , x 2 , x 3.. x s i z ) , s i z 为 儿 子 的 数 目 val_x=lcm(x1,x2,x3..x_{siz}),siz为儿子的数目 valx​=lcm(x1,x2,x3..xsiz​),siz为儿子的数目 把这个结论扩大整张图来说,我们知道确定了根的赋值后,整个树的值都会确定.如何来满足每个结点都满足上述的等式呢. v a l y = ( v a l x ∗ y ) / x val_y=(val_x*y)/x valy​=(valx​∗y)/x 当且仅当 v a l x ∗ y val_x*y valx​∗y的所有素数因子的幂大于等于 x x x的时候,才有整除成立. 反过来说,当前点的赋值 v a l x val_x valx​与 y 的 y的 y的乘积的某个素数因子不够的时候,上述关系就会失效.那么当素数因子不够的时候怎么办,只能多给它赋值. 假 设 缺 少 p k 假设缺少p^k 假设缺少pk,这就势必会让该点到根的路径上所有的点都要乘上 p k p^k pk.所以不如从根上直接乘上 p k p^k pk. 但我们可以观察到对于每一个点来说,同一个素数 p p p需求的幂次 k k k是不同的,因为我们是看 v a l x ∗ y val_x*y valx​∗y与 x x x的对应素数来说缺了多少的 k k k次. 对于一个素数 p p p来说,对于点 i i i来说对于它的需求记为 n e e d ( p , i ) need(p,i) need(p,i),那么在根上对应素数幂次的取值就是 m a x ( n e e d ( p , i ) ) max(need(p,i)) max(need(p,i)) 那么作法也十分显然了,对这根树进行dfs,那么对于每条边的信息 y , x y,x y,x。 y 的 对 应 素 数 贡 献 是 1 , 代 表 补 充 v a l x , x 的 贡 献 是 − 1 , 代 表 需 求 该 素 数 y的对应素数贡献是1,代表补充val_x,x的贡献是-1,代表需求该素数 y的对应素数贡献是1,代表补充valx​,x的贡献是−1,代表需求该素数. 用一个数组 n e e d ( p ) , 记 录 每 个 素 数 需 求 的 次 数 , n e e d ( p ) 的 更 新 就 是 d f s 过 程 中 每 个 点 对 应 素 数 p 需 求 的 最 大 贡 献 . need(p),记录每个素数需求的次数,need(p)的更新就是dfs过程中每个点对应素数p需求的最大贡献. need(p),记录每个素数需求的次数,need(p)的更新就是dfs过程中每个点对应素数p需求的最大贡献. 最后根的取值就是 ∏ p n e e d ( p ) \prod{p^{need(p)}} ∏pneed(p). 再根据根的最佳取值去更新每个点的答案,统计答案即可. 注意, c n t cnt cnt数组的更新是包含回溯的,因为不同子树之间的素数因子是没有影响的. 再注意,t很大,随便memset超时警告. Ac代码:

/*
*/
#include
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
const int N = 2e5;
const int INF = 1e9+7;
typedef pair pii;
const int mod = 998244353;
#define int long long
int vis[maxn];
struct Edge{
	int v,x,y;
};
vector G[maxn];
vector fac[maxn];
int cnt[maxn];//prime_fac
int need[maxn];
int f_pow(int a,int b){
	int ans =1;
	while(b){
		if(b&1) ans = (ans*a)%mod;
		b>>=1;a=(a*a)%mod;
	}
	return ans%mod;
}
ll ans = 0;
void init(int n){
	for(int i=0;iu>>v>>x>>y;
			G[u].push_back({v,x,y});
			G[v].push_back({u,y,x});
		}
		//第一次dfs,得到need数组 
		dfs1(1,0);
		ll val = 1;//根的值
		for(int i=2;i