大致题意：给定若干组询问，每次给定一个 $n$，代表一共有 $n$ 个节点，点权分别为 $1$ ~ $n$，任意两点都可以连边，边权为两个点权的 $\gcd$，现在求生成一棵最大生成树。

$n \le 1e5$

个人思路：枚举每个 $n$，拿它和它的倍数去连边，然后排序，跑克鲁斯卡尔算法求解。

结果 TLE。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

const int N = 1e5 + 5;

struct Graph {
    int v, nxt, w;
}e[N << 1];

struct Edge {
    int u, v, w;
}a[N << 2];

int lk[N], ltp;

int cnt;

int dad[N];
bool vis[N * 5];

int anc(int x) {
    if(dad[x]) return dad[x] = anc(dad[x]);
    return x;
}

bool ask(int x, int y) {
    return x == y;
}

void uni(int x, int y) {
    if(x != y)
        dad[x] = y;
}

bool cmp(Edge x, Edge y) {
    return x.w > y.w;
}

int main() {
    int n;
    while(cin >> n) {
        memset(a, 0, sizeof(a));
        memset(dad, 0, sizeof(dad));
        cnt = 0;

        for(int i = 1; i <= n / 2; i++)
            for(int j = 2; i * j <= n; j++)
                    a[++cnt] = (Edge){i, i * j, i};

        sort(a + 1, a + 1 + cnt, cmp);

        int ans = 0;
        for(int i = 1; i <= cnt; i++) {
            a[i].u = anc(a[i].u), a[i].v = anc(a[i].v);
            if(!ask(a[i].u, a[i].v)) {
                uni(a[i].u, a[i].v);
                ans += a[i].w;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

/*
1
2
3
4
5
*/