Problem GCD Tree
题目大意
n个点的无向完全图，标号1~n，每条边u-->v 的权值为gcd（u,v），求其最大生成树，输出最大边权和。
n<=10^5，有多个询问。
解题分析
从小到大加入每个点，计算其对答案的贡献。
对于一个点i，只有向它的约数连边才有可能对答案有贡献。
用lct维护一棵最大生成树即可。
参考程序
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std; #define N 400008
#define M 50008
#define LL long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define clr(x,v) memset(x,v,sizeof(x));
#define bitcnt(x) __builtin_popcount(x)
#define rep(x,y,z) for (int x=y;x<=z;x++)
#define repd(x,y,z) for (int x=y;x>=z;x--)
const int mo = ;
const int inf = 0x3f3f3f3f;
const int INF = ;
/**************************************************************************/
const int maxn = ;
vector <int> p[N]; int n,m;
int fa[N],val[N],mn[N],rev[N],c[N][],st[N],ln[N],rn[N];
LL ans[maxn]; bool isroot(int k){
return c[fa[k]][]!=k && c[fa[k]][]!=k;
}
void pushup(int x){
int l=c[x][],r=c[x][];
mn[x]=x;
if (val[mn[l]]<val[mn[x]]) mn[x]=mn[l];
if (val[mn[r]]<val[mn[x]]) mn[x]=mn[r];
}
void pushdown(int x){
int l=c[x][],r=c[x][];
if (rev[x]){
if (l) rev[l]^=;
if (r) rev[r]^=;
rev[x]^=;
swap(c[x][],c[x][]);
}
}
void rotate(int x){
int y=fa[x],z=fa[y],l,r;
if (c[y][]==x) l=; else l=; r=l^;
if (!isroot(y)){
if (c[z][]==y) c[z][]=x; else c[z][]=x;
}
fa[x]=z; fa[y]=x; fa[c[x][r]]=y;
c[y][l]=c[x][r]; c[x][r]=y;
pushup(y); pushup(x);
}
void splay(int x){
int top=; st[++top]=x;
for (int i=x;!isroot(i);i=fa[i]) st[++top]=fa[i];
while (top) pushdown(st[top--]);
while (!isroot(x)){
int y=fa[x],z=fa[y];
if (!isroot(y)){
if (c[y][]==x^c[z][]==y) rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x){
int t=;
while (x){
splay(x);
c[x][]=t;
pushup(x);
t=x; x=fa[x];
}
}
void rever(int x){
access(x); splay(x); rev[x]^=;
}
void link(int u,int v){
rever(u); fa[u]=v;
}
void cut(int u,int v){
rever(u); access(v); splay(v); fa[c[v][]]=; c[v][]=; pushup(v);
}
int find(int u){
access(u); splay(u);
while (c[u][]) u=c[u][];
return u;
}
int query(int u,int v){
rever(u); access(v); splay(v); return mn[v];
}
int main(){
for (int i=;i<=maxn;i++)
for (int j=i;j<=maxn;j+=i)
p[j].push_back(i);
int now=;
val[]=INF;
rep(i,,maxn){
val[++now]=INF;
mn[now]=now;
}
ans[]=;
LL tmp=;
for (int u=;u<=maxn;u++){
for (int i=p[u].size()-;i>=;i--)
{
int v=p[u][i];
int flag=;
if (find(u)==find(v)){
int t=query(u,v);
if (v>val[t]){
cut(ln[t],t);
cut(rn[t],t);
tmp-=val[t];
flag=;
}
else flag=;
}
if (flag){
mn[++now]=now; val[now]=v; ln[now]=u; rn[now]=v;
link(now,u); link(now,v);
tmp+=v;
}
}
ans[u]=tmp;
}
while (~scanf("%d",&n)){
printf("%lld\n",ans[n]);
}
}