Atcoder ABC282E Choose Two and Eat One

https://atcoder.jp/contests/abc282/tasks/abc282_e

发现选出两个球去掉一个球其实很像一颗树去掉叶子节点，贡献即为叶子节点与父亲的边权。

那这题就很明显了，预处理好每两个数产生的贡献，跑一个最大生成树即可。

时间复杂度 \(O(n\sum \log a_i + n^2\log n^2)\)。

# include <bits/stdc++.h>
using namespace std;
const int N = 500 + 10;
struct line {
    int u, v;
    long long w;
} a [N * N];
long long m;
long long qmi (long long a, long long b) {
    long long tot = 1;
    while (b) {
        if (b & 1) {
            tot *= a;
            tot %= m;
        }
        a *= a;
        a %= m;
        b >>= 1;
    }
    return tot;
}// 快速幂
long long p [N];
int fa [N];
int find (int x) {
    if (fa [x] == x) {
        return x;
    }
    return fa [x] = find (fa [x]);
}
int main () {
    int n;
    scanf ("%d %lld", & n, & m);
    for (int i = 1; i <= n; ++ i) {
        scanf ("%lld", & p [i]);
    }
    int cnt = 0;
    for (int i = 1; i <= n; ++ i) {
        for (int j = i + 1; j <= n; ++ j) {
            a [++ cnt] = {i, j, (qmi (p [i], p [j]) + qmi (p [j], p [i])) % m};
        }
    }// 处理好贡献
    sort (a + 1, a + cnt + 1, [] (line a, line b) {
        return a .w > b .w;
    });
    for (int i = 1; i <= n; ++ i) {
        fa [i] = i;
    }
    long long ans = 0;
    for (int i = 1, j = 0; j < n - 1; ++ i) {
        int u = find (a [i] .u), v = find (a [i] .v);
        if (u != v) {
            ans += a [i] .w;
            fa [u] = v;
            ++ j;
        }
    }// 最大生成树
    printf ("%lld", ans);
    return 0;
}