CF959E

jijidawang · 2022-05-31 17:38:38 · 题解

从 0 编号真难受啊

考虑归纳 .

令 n-1 个节点的答案为 f(n)，则加一个节点 n-1 就和前面所有点连一条边 .

根据 Prim 原理，只需要挑一条最小的和 n-1 连着的边然后加进 MST 里就好了 .

现在的问题是最小边的边权是多少，显然就是

于是 f(n)=f(n-1)+\operatorname{lowbit}(n-1) .

简单处理一下边界就可以得到通项公式：

按位考虑，钦定一个 \operatorname{lowbit}(i) 然后更高位随便选，这样就是 O(\log n) 的了 .

核心代码，仅供参考

ll x, ans;
int main()
{
    scanf("%lld", &x); --x;
    for (int i=0; x>>i; i++) ans += ((x >> i) - (x >> (i+1))) * (1ll << i);
    printf("%lld\n", ans); 
    return 0;
}