社区讨论

求助站外题

大大眼仔Happy
学术版参与者 2已保存回复 10

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
10 条
当前快照
1 份
快照标识符
@lo8u1af3
此快照首次捕获于
2023/10/28 00:33
2 年前
此快照最后确认于
2023/10/28 00:33
2 年前
查看原帖
题目：
给出一棵无根树。
然后有以下定义：
a[i]a[i]表示ii号点的值
size[u][v]size[u][v]表示uu到vv的最短路径的点数
gcd[u][v]gcd[u][v]表示uu到vv的最短路径的节点的最大公约数
cost[u][v]=size[u][v]×gcd[u][v]cost[u][v]=size[u][v]\times gcd[u][v]
求：
∑i=1n−1∑j=i+1ncost[i][j]\sum^{n-1}_{i=1}\sum^{n}_{j=i+1}cost[i][j]
数据范围：
n≤105n\leq 10^5，ai≤106a_i\leq 10^6
求助大佬（这道题我直接暴力LCA的）

回复

共 10 条回复，欢迎继续交流。

正在加载回复...