还没打完数学专题呢就来打这个了。（其实是不会多项式）
难度大概升序。
Giving Awards
注意到一个关键信息：每对人只会被提到一次。所以一定有解。
考虑卡bug，假如\(a\)欠\(b\)钱，那么就先让\(b\)取钱再让\(a\)取钱，建边dfs即可，注意图不连通。
点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
auto I = freopen("in.in","r",stdin),O = freopen("out.out","w",stdout);
#else
auto I = stdin,O = stdout;
#endif
using ll = long long;using ull = unsigned long long;
using db = long double;using ldb = long double;
const int N = 3e4 + 10;
#define eb emplace_back
vector<int> e[N],ans;
bitset<N> vis;
int n,m,d[N];
void dfs(int x,int fa){
vis[x] = true;
for(auto y:e[x]){
if(vis[y]) continue;
dfs(y,x);
}
ans.emplace_back(x);
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n>>m;
rep(i,1,m,1){int x,y;cin>>x>>y;e[x].eb(y);}
rep(i,1,n,1) if(!vis[i]) dfs(i,0);
for(auto i:ans) cout<<i<<' ';
}
[BJWC2010] 严格次小生成树
一个结论：次小生成树与最小生成树只会有一条边不同。
先将最小生成树求出来，然后考虑所有的非树边，发现这条边\((u,v,w)\)替换的必定是\(u\rightarrow LCA(u,v),v\rightarrow LCA(u,v)\)上的一条边\((u^\prime,v^\prime,w^\prime),w^\prime < w\)。
那么现在就是求\(u\rightarrow v\)的简单路径上所有的边中，\(w\)的前驱。
不会倍增，只会树剖+线段树，考虑将所有树边排序，每次查询非树边时，将所有权值小于它的假如，然后求链上最大值即可，但是边权不好做，考虑边权转点权即可，时间复杂度\(O(m\log^2 n)\)，但是由于树剖常数小，跑的和倍增差不多，而且空间比倍增优秀。
点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
auto I = freopen("in.in","r",stdin),O = freopen("out.out","w",stdout);
#else
auto I = stdin,O = stdout;
#endif
using ll = long long;using ull = unsigned long long;
using db = long double;using ldb = long double;
#define eb emplace_back
const int N = 1e5 + 10,M = 3e5 + 10;
vector<pair<int,int> > e[N];
int n,m;struct node{int x,y,z;}edge[M];
bitset<M> unused;
int dist[N],top[N],siz[N],son[N],dfn[N],rdfn[N],tim,dep[N],fa[N];
struct DSU{
vector<int> fa;
void init(int n){fa.resize(n+1);rep(i,1,n,1) fa[i] = i;}
int get_fa(int x){while(x ^ fa[x]) x = fa[x] = fa[fa[x]];return x;}
bool Merge(int x,int y){
x = get_fa(x),y = get_fa(y);
if(x == y) return false;
return fa[x] = y,true;
}
}D;
struct Segment_Tree{
struct segment_tree{
int l,r,val;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define val(x) tree[x].val
}tree[N<<2];
void B(int k = 1,int l = 1,int r = n){
l(k) = l,r(k) = r;
if(l == r) return;
int mid = (l + r) >> 1;
B(k<<1,l,mid);B(k<<1|1,mid+1,r);
}
void upd(int k,int pos,int val){
if(l(k) == r(k)) return val(k) = val,void();
int mid = (l(k) + r(k)) >> 1;
pos <= mid?upd(k<<1,pos,val):upd(k<<1|1,pos,val);
val(k) = max(val(k<<1),val(k<<1|1));
}
int qry(int k,int l,int r){
if(l <= l(k) && r(k) <= r) return val(k);
int mid = (l(k) + r(k)) >> 1,res = 0;
if(l <= mid) res = max(res,qry(k<<1,l,r));
if(r > mid) res = max(res,qry(k<<1|1,l,r));
return res;
}
}T;
void dfs1(int x){
siz[x] = 1,dep[x] = dep[fa[x]] + 1;
for(auto [y,w]:e[x]){
if(y == fa[x]) continue;
fa[y] = x;dfs1(y);dist[y] = w;
siz[x] += siz[y];
if(siz[son[x]] < siz[y]) son[x] = y;
}
}
void dfs2(int x,int t){
top[x] = t;rdfn[dfn[x] = ++tim] = x;
if(son[x]) dfs2(son[x],t);else return;
for(auto [y,w]:e[x]){
if(y == fa[x] || y == son[x]) continue;
dfs2(y,y);
}
}
int query(int x,int y){
int fx = top[x],fy = top[y];
int res = 0;
while(fx ^ fy){
if(dep[fx] < dep[fy]) swap(x,y),swap(fx,fy);
res = max(res,T.qry(1,dfn[fx],dfn[x]));
x = fa[fx];fx = top[x];
}
if(dep[x] > dep[y]) swap(x,y);
if(x == y) return res;
res = max(res,T.qry(1,dfn[x]+1,dfn[y]));
return res;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n>>m;rep(i,1,m,1) cin>>edge[i].x>>edge[i].y>>edge[i].z;
D.init(n);
sort(edge+1,edge+1+m,[](node x,node y){return x.z < y.z;});
ll total = 0;
rep(i,1,m,1){
auto [x,y,w] = edge[i];
auto flag = D.Merge(x,y);
if(!flag){unused[i] = true;continue;}
e[x].eb(y,w);e[y].eb(x,w);total += w;
}
dfs1(1);dfs2(1,1);T.B();
int ans = 1e9;
int now = 1;
rep(i,1,m,1){
auto [x,y,w] = edge[i];
while(now <= m && edge[now].z < w){
if(unused[now]){now++;continue;}
auto [x,y,w] = edge[now];
if(fa[x] == y) T.upd(1,dfn[x],edge[now].z);
if(fa[y] == x) T.upd(1,dfn[y],edge[now].z);
now++;
}
if(!unused[i]) continue;
if(x == y) continue;
int res = w-query(x,y);
ans = min(ans,res);
}
cout<<total + ans<<'\n';
}
跳楼机
同余最短路板子，当个学习笔记写。
当出现形如
- 给定 \(n\) 个整数，求这 \(n\) 个整数能拼凑出多少的其他整数 （\(n\) 个整数可以重复取）。
- 给定 \(n\) 个整数，求这 \(n\) 个整数不能拼凑出的最小（最大）的整数。
- 至少要拼几次才能拼出模 \(K\) 余 \(p\) 的数
等问题时可以使用同余最短路的方法。
既然带了最短路，那么就类比最短路。同余最短路中的转移通常是\(f(i+y)=f(i)+y\)，类比\(dist_v=dist_u+e(u,v)\)。
考虑这道题，设\(d_i\)表示只通过\(2,3\)操作，满足\(p\bmod x=i\)的最小的\(p\)，那么就有\(f((i+y)\bmod x)=f(i)+y,f((i+z)\bmod x)=f(i)+z\)。实质上就是最短路中的加边操作，接下来只需要求出\(d_0,d_1,\ldots,d_{x-1}\)即可，答案为\(\sum\limits_{i=0}^{x-1}[h\ge d_i](\frac{h-d_i}{x}+1)\)。但是由于本题\(h\le 2^{63}-1\)，求解时\(d\)的初值至少应为\(2^63>LLONG\_MAX\)，所以可以将\(h\leftarrow h-1\)，将初始楼层设为\(0\)即可。
点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
auto I = freopen("in.in","r",stdin),O = freopen("out.out","w",stdout);
#else
auto I = stdin,O = stdout;
#endif
using ll = long long;using ull = unsigned long long;
using db = long double;using ldb = long double;
#define int ull
const int N = 1e5 + 10;
int h,x,y,z,dist[N];
vector<pair<int,int> > e[N];
bitset<N> vis;
void dijkstra(){
memset(dist,0x3f,sizeof dist);
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
q.emplace(0,0);dist[0] = 0;
while(q.size()){
int x = q.top().second;q.pop();
if(vis[x]) continue;
vis[x] = true;
for(auto [y,w]:e[x]){
if(dist[y] > dist[x] + w){
dist[y] = dist[x] + w;
q.emplace(dist[y],y);
}
}
}
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>h>>x>>y>>z;h--;
rep(i,0,x-1,1){
e[i].emplace_back((i+y)%x,y);
e[i].emplace_back((i+z)%x,z);
}
dijkstra();
int ans = 0;
rep(i,0,x-1,1) if(h >= dist[i]) ans += (h-dist[i])/x+1;
cout<<ans<<'\n';
}
[国家集训队] 墨墨的等式
显然答案具有可差分性，考虑求出\([0,l),[0,r]\)中的可以凑出的值作差即可，处理方法同上。
点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
auto I = freopen("in.in","r",stdin),O = freopen("out.out","w",stdout);
#else
auto I = stdin,O = stdout;
#endif
using ll = long long;using ull = unsigned long long;
using db = long double;using ldb = long double;
const int N = 5e5 + 10;
int n,x;bitset<N> vis;
vector<pair<int,int> > e[N];
ll l,r,dist[N];
vector<int> num;
void dijkstra(int s){
memset(dist,0x3f,sizeof dist);
priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > q;
q.emplace(0,0);dist[0] = 0;
while(q.size()){
int x = q.top().second;q.pop();
if(vis[x]) continue;
vis[x] = true;
for(auto [y,w]:e[x]){
if(dist[y] > dist[x] + w){
dist[y] = dist[x] + w;
q.emplace(dist[y],y);
}
}
}
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n>>l>>r>>x;l--;
rep(i,2,n,1){int x;cin>>x;num.emplace_back(x);}
rep(i,0,x-1,1) for(auto j:num) e[i].emplace_back((i+j)%x,j);
dijkstra(0);
ll ans = 0;
rep(i,0,x-1,1) if(l >= dist[i]) ans -= (l-dist[i])/x+1;
rep(i,0,x-1,1) if(r >= dist[i]) ans += (r-dist[i])/x+1;
cout<<ans<<'\n';
}
Fairy
【模板】线段树分治
线段树分治太naive了，考虑换个优秀的做法。
显然答案为奇环交，考虑如何求这个。考虑跑一遍dfs，求出一颗生成树。
对于一条非树边，显然会形成一个环，称这个环上的树边被其覆盖。
如果一条非树边和树边形成一个有且仅有这一条非树边的奇环，那么称这条非树边为坏边。
显然答案边被所有坏边覆盖，且不被好边覆盖。
然后直接树上差分就可以了，时间复杂度\(O(n)\)。
点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
auto I = freopen("in.in","r",stdin),O = freopen("out.out","w",stdout);
#else
auto I = stdin,O = stdout;
#endif
using ll = long long;using ull = unsigned long long;
using db = long double;using ldb = long double;
const int N = 1e4 + 10;
#define eb emplace_back
vector<int> e[N],id[N],ans;
bitset<N> vis;
bool dis[N],ok[N];
int s[N],ct,eid,n,m;
void dfs(int x){
vis[x] = true;
rep(i,0,(int)e[x].size()-1,1){
int y = e[x][i];
if(!vis[y]){
dis[y] = dis[x]^1;
ok[id[x][i]] = 1;dfs(y);
}
else if(!ok[id[x][i]]){
ok[id[x][i]] = 1;
if(dis[y] == dis[x]){
ct++;s[x]++;s[y]--;
eid = id[x][i];
}
else s[x]--,s[y]++;
}
}
}
void dfs1(int x){
vis[x] = true;
rep(i,0,(int)e[x].size() - 1,1){
int y = e[x][i];
if(!vis[y]){
dfs1(y);
if(s[y] == ct) ans.emplace_back(id[x][i]);
s[x] += s[y];
}
}
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n>>m;
rep(i,1,m,1){
int u,v;cin>>u>>v;
e[u].eb(v);e[v].eb(u);
id[u].eb(i);id[v].eb(i);
}
rep(i,1,n,1) if(!vis[i]) dfs(i);
if(!ct){
cout<<m<<'\n';
rep(i,1,m,1) cout<<i<<' ';
return 0;
}
vis.reset();
rep(i,1,n,1) if(!vis[i]) dfs1(i);
if(ct == 1) ans.emplace_back(eid);
cout<<ans.size()<<'\n';
sort(ans.begin(),ans.end());
for(auto i:ans) cout<<i<<' ';
}
[中山市选] 杀人游戏
一眼下去答案为\(\frac{n-缩点后入度为0的点的个数}{n}\)。然后喜提30pts。
考虑哪里有问题呢？贪心的想，我们可以将强连通分量中个数为\(1\)且所连的点的入度都\(>1\)的点放在最后一个询问，如果其它点都确定了，那么这个点显然不用问，答案为\(\frac{n-缩点后入度为0的点的个数}{n}\)。
本题卡精度，输出答案时应加上eps。
点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
auto I = freopen("in.in","r",stdin),O = freopen("out.out","w",stdout);
#else
auto I = stdin,O = stdout;
#endif
using ll = long long;using ull = unsigned long long;
using db = long double;using ldb = long double;
const int N = 1e5 + 10;
#define eb emplace_back
int n,m;vector<int> e[N];
int dfn[N],low[N],tim,sta[N],top;
int tot = 0,g[N],u[N],v[N],d[N],siz[N],ct[N],out[N];
bitset<N> insta;set<int> pd[N];
void Tarjan(int x){
dfn[x] = low[x] = ++tim;
sta[++top] = x;insta[x] = true;
for(auto y:e[x]){
if(!dfn[y]) Tarjan(y),low[x] = min(low[x],low[y]);
else if(insta[y]) low[x] = min(low[x],dfn[y]);
}
if(dfn[x] == low[x]){
int y;tot++;
do{
y = sta[top--];
g[y] = tot;
insta[y] = false;
siz[tot]++;
}while(y != x);
}
}
vector<pair<int,int> > E;
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n>>m;
rep(i,1,m,1){
int u,v;cin>>u>>v;
if(pd[u].count(v)) continue;
pd[u].insert(v);
e[u].eb(v);E.eb(u,v);
}
rep(i,1,n,1) pd[i].clear();
rep(i,1,n,1) if(!dfn[i]) Tarjan(i);
for(auto [x,y]:E){
if(g[x] == g[y]) continue;
if(pd[g[x]].count(g[y])) continue;
pd[g[x]].insert(g[y]);
out[g[x]]++;
d[g[y]]++;
}
ldb ans = 0;
for(auto [x,y]:E){
if(g[x] == g[y]) continue;
if(d[g[y]] >= 2) ct[g[x]]++;
}
rep(i,1,tot,1){
if(!d[i] && ct[i] == out[i] && siz[i] == 1){ans -= 1;break;}
}
rep(i,1,tot,1){if(!d[i])ans += 1;}
cout<<fixed<<setprecision(6);
cout<<1.0*(n-ans)/n+1e-9<<'\n';
}
[NOI2018] 归程
模板：kruskal重构树。
就是用kruskal时，将两个点中间创建一个虚点，点权记为边权。
有如下性质：
- 两个点之间的所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = Kruskal 重构树上两点之间的 LCA 的权值。
- 如果以最小生成树的方式建树，那么建出的树是大根堆的形式。
本题则求最大生成树，就利用小根堆的性质，建出kruskal重构树后，每个点维护子树内\(1\)到子树内的点的最小值。
由于不会倍增，考虑树剖暴力跳，如果发现链顶无法达到，那么就在这条重链上二分即可。注意树剖清空，不然会导致奇怪错误。
时间复杂度\(O(m\log m + q\log n)\)。
点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
auto I = freopen("in.in","r",stdin),O = freopen("out.out","w",stdout);
#else
auto I = stdin,O = stdout;
#endif
using ll = long long;using ull = unsigned long long;
using db = long double;using ldb = long double;
#define int ll
#define eb emplace_back
const int N = 4e5 + 10;
vector<pair<int,int> > e[N],t[N];
struct Edge{int x,y,l,a;}edge[N];
int n,m,vtot,fa[N],siz[N],son[N],top[N],dfn[N],rdfn[N],tim,dep[N],dis[N],lastans;
int v,p,q,k,s;
ll dist[N];
bitset<N> vis;
void dijkstra(int s = 1){
memset(dist,0x3f,sizeof dist);vis.reset();
priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > q;
dist[s] = 0;q.emplace(0,s);
while(q.size()){
int x = q.top().second;q.pop();
if(vis[x]) continue;
vis[x] = true;
for(auto [y,w]:e[x]){
if(dist[y] > dist[x] + w){
dist[y] = dist[x] + w;
q.emplace(dist[y],y);
}
}
}
}
struct DSU{
vector<int> fa;
void init(int n){fa.resize(n+1); rep(i,1,n,1) fa[i] = i;}
int get_fa(int x){while(x ^ fa[x]) x = fa[x] = fa[fa[x]];return x;}
bool Merge(int x,int y){
x = get_fa(x),y = get_fa(y);
if(x == y) return false;
if(x > y) swap(x,y);
return fa[x] = y,true;
}
}D;
void dfs1(int x){
dep[x] = dep[fa[x]] + 1;siz[x] = 1;
for(auto [y,w]:t[x]){
if(y == fa[x]) continue;
dis[y] = w;fa[y] = x;dfs1(y);
siz[x] += siz[y];
dist[x] = min(dist[x],dist[y]);
if(siz[son[x]] < siz[y]) son[x] = y;
}
}
void dfs2(int x,int tp){
top[x] = tp;rdfn[dfn[x] = ++tim] = x;
if(son[x]) dfs2(son[x],tp);else return;
for(auto [y,w]:t[x]){
if(y == fa[x] || y == son[x]) continue;
dfs2(y,y);
}
}
void init(){
rep(i,1,n*2+10,1) e[i].clear(),t[i].clear();
memset(fa,0,sizeof fa);memset(siz,0,sizeof siz);
memset(dfn,0,sizeof dfn);memset(rdfn,0,sizeof rdfn);
memset(dep,0,sizeof dep);memset(top,0,sizeof top);
memset(son,0,sizeof son);
sort(edge+1,edge+1+m,[](Edge x,Edge y){return x.a > y.a;});
D.init(n*2+10);
rep(i,1,m,1){
auto [x,y,l,a] = edge[i];
e[x].eb(y,l);e[y].eb(x,l);
if(D.get_fa(x) == D.get_fa(y)) continue;
vtot++;
t[vtot].eb(D.get_fa(x),a);t[vtot].eb(D.get_fa(y),a);
t[D.get_fa(x)].eb(vtot,a);t[D.get_fa(y)].eb(vtot,a);
D.fa[D.get_fa(x)] = vtot;D.fa[D.get_fa(y)] = vtot;
}
dijkstra();dfs1(vtot);tim = 0;dfs2(vtot,vtot);
}
int get(int v,int p){
int x = v,fx = top[x];
while(x && dis[fx] > p) x = fa[fx],fx = top[x];
int l = dfn[fx],r = dfn[x],res = 0;
while(l <= r){
int mid = (l + r) >> 1;
if(dis[rdfn[mid]] <= p) res = rdfn[mid],l = mid + 1;
else r = mid - 1;
}
if(!res || res == 1) return 0;
return dist[res];
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int T;cin>>T;
rep(Test,1,T,1){
cin>>n>>m;vtot = n;lastans = 0;
rep(i,1,m,1)cin>>edge[i].x>>edge[i].y>>edge[i].l>>edge[i].a;
init();cin>>q>>k>>s;
rep(test,1,q,1){
cin>>v>>p;
v = (v+k*lastans - 1)%n+1;p = (p+k*lastans)%(s+1);
cout<<(lastans = get(v,p))<<'\n';
}
}
}
Xor-MST
考虑Boruvka算法，那么就只需要考虑如果对于每个点，快速求出不在其连通块中最小连边。
求异或最小值，考虑01-trie，建一个全局trie，然后对于每个连通块，维护每个连通块的trie，然后记录每个节点的size，对于每个点，在全局trie中查找，如果减去其所在连通块中的size仍有，正常跑就行，合并两个连通块的时候，启发式合并它们的trie即可。
时间复杂度\(O(n\log n\log V)\)，空间复杂度\(O(n\log V)\)。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
auto I = freopen("in.in","r",stdin),O = freopen("out.out","w",stdout);
#else
auto I = stdin,O = stdout;
#endif
using ll = long long;using ull = unsigned long long;
using db = long double;using ldb = long double;
const int N = 2e5 + 10;
const ll inf = 1e15;
int n,a[N],rt[N],to[N];
ll mn[N];
struct Trie{
int tree[N*60][2],siz[N*60],tot,ed[N*60];
void insert(int &x,int dep,int w,int id){
if(!x) x = ++tot;
if(dep < 0) return ed[x] = id,siz[x] = 1,void();
int c = w>>dep&1;
insert(tree[x][c],dep-1,w,id);siz[x]++;
}
int Merge(int x,int y){
if(!x || !y) return x|y;
tree[x][0] = Merge(tree[x][0],tree[y][0]);
tree[x][1] = Merge(tree[x][1],tree[y][1]);
siz[x] = siz[tree[x][0]] + siz[tree[x][1]];
ed[x] = ed[y];
return x;
}
pair<int,int> get(int x,int pre,int w){
int ans = 0;
drep(i,30,0,1){
int c = w>>i&1;
if(tree[x][c] && siz[tree[x][c]] - siz[tree[pre][c]] > 0)
x = tree[x][c],pre = tree[pre][c];
else ans |= 1<<i,x = tree[x][c^1],pre = tree[pre][c^1];
}
return make_pair(ans,ed[x]);
}
}T;
struct DSU{
vector<int> fa,siz;int tot;
void init(int n){tot = n;fa.resize(n+1),siz.resize(n+1,1);rep(i,1,n,1) fa[i] = i;}
int get_fa(int x){while(x ^ fa[x]) x = fa[x] = fa[fa[x]];return x;}
pair<int,int> Merge(int x,int y){
x = get_fa(x),y = get_fa(y);
if(x == y) return make_pair(0,0);
tot--;
if(siz[x] > siz[y]) swap(x,y);
fa[x] = y;siz[y] += siz[x];
return make_pair(x,y);
}
}D;
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
vector<int> num;
cin>>n;rep(i,1,n,1) cin>>a[i],num.emplace_back(a[i]);
sort(a+1,a+1+n);n = unique(a+1,a+1+n) - a - 1;
rep(i,1,n,1) T.insert(rt[0],30,a[i],i),T.insert(rt[i],30,a[i],i);
D.init(n);bitset<N> vis;
ll ans = 0;int tot = 0;
while(D.tot != 1){
tot++;
rep(i,1,n,1) mn[i] = inf;
rep(i,1,n,1){
auto res = T.get(rt[0],rt[D.get_fa(i)],a[i]);
if(res.first < mn[D.get_fa(i)])
mn[D.get_fa(i)] = res.first,to[D.get_fa(i)] = D.get_fa(res.second);
}
bool flag = true;
rep(i,1,n,1){
if(mn[i] == inf) continue;
flag &= false;
auto res = D.Merge(i,to[i]);
if(res.first) T.Merge(rt[res.second],rt[res.first]),ans += mn[i];
}
}
cout<<ans<<'\n';
}
\(to\;be\;continued\)
标签：图论,专题,dist,fa,省选,rep,long,int,using From： https://www.cnblogs.com/hzoi-Cu/p/18624994