kruscal重构树
模板
- 如果是最小生成树，那么u,v之间路径的最小边权最大值，即为lca(u,v)的权值
- 如果是最大生成树，那么为最大边权最小值
cpp
void Ex_kruscal(){
sort(e.begin(),e.end());
dsu.init(2*n+1);
for(auto [u,v,c]:e){
if(dsu.same(u,v))continue;
++idx;
u=dsu.find(u),v=dsu.find(v);
adj[idx].push_back(u);
adj[idx].push_back(v);
dsu.merge(idx,u);
dsu.merge(idx,v);
w[idx]=c;
}
}P4197 Peaks
题意：
n座山峰，每座山峰高度为hi
m条路径，每条路径有困难度w
q组询问，v x k求从v开始只经过小于等于x的边能到达的点，山峰第k大值
思路：
- 重构树，倍增找出第一个小于等于x的祖先
- 接下来就是求第k小的问题，建出dfs序，主席树查询
cpp
struct Edge{
int u,v,w;
bool operator<(const Edge&tmp)const{
return w<tmp.w;
}
};
struct DSU{
vector<int> par;
void init(int n){
par.resize(n,0);
iota(par.begin(),par.end(),0);
}
int find(int x){
return par[x]==x?x:par[x]=find(par[x]);
}
bool merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return false;
par[y]=x;
return true;
}
bool same(int x,int y){
return find(x)==find(y);
}
} dsu;
int idx,n,m,q,ts,w[N],dfn[N],siz[N],nw[N],h[N],par[N][30];
vector<int> adj[N];
vector<Edge> e;
void Ex_kruscal(){
sort(e.begin(),e.end());
dsu.init(2*n+1);
for(auto [u,v,c]:e){
if(dsu.same(u,v))continue;
++idx;
u=dsu.find(u),v=dsu.find(v);
adj[idx].push_back(u);
adj[idx].push_back(v);
dsu.merge(idx,u);
dsu.merge(idx,v);
w[idx]=c;
}
}
void dfs(int u,int fa){
dfn[u]=++ts;
if(adj[u].size())nw[ts]=-1;
else nw[ts]=h[u];
par[u][0]=fa;
for(int i=1;i<=25;i++)par[u][i]=par[par[u][i-1]][i-1];
siz[u]=1;
for(auto v:adj[u]){
dfs(v,u);
siz[u]+=siz[v];
}
}
struct Node{
int ls,rs,cnt;
};
struct SegmentTree{
vector<Node> t;
void init(int n){
t=vector<Node>(n<<5);
}
void pushup(int p){
t[p].cnt=t[t[p].ls].cnt+t[t[p].rs].cnt;
}
int build(int l,int r){
int p=++idx;
if(l==r)return p;
int mid=l+r>>1;
t[p].ls=build(l,mid);
t[p].rs=build(mid+1,r);
return p;
}
int insert(int p,int l,int r,int x){
int q=++idx;
t[q]=t[p];
if(l==r){
t[q].cnt++;
return q;
}
int mid=l+r>>1;
if(x<=mid)t[q].ls=insert(t[p].ls,l,mid,x);
else t[q].rs=insert(t[p].rs,mid+1,r,x);
pushup(q);
return q;
}
int query(int p,int q,int l,int r,int k){
if(l==r)return l;
int mid=l+r>>1;
int cnt=t[t[q].ls].cnt-t[t[p].ls].cnt;
if(k<=cnt)return query(t[p].ls,t[q].ls,l,mid,k);
return query(t[p].rs,t[q].rs,mid+1,r,k-cnt);
}
} seg;
void solve(){
cin>>n>>m>>q;
idx=n;
vector<int> nums;
for(int i=1;i<=n;i++)cin>>h[i],nums.push_back(h[i]);
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());
for(int i=1;i<=n;i++)h[i]=lower_bound(nums.begin(),nums.end(),h[i])-nums.begin();
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
e.push_back({u,v,w});
}
Ex_kruscal();
dfs(idx,0);
int NN=nums.size()-1;
seg.init(NN);
vector<int> root(ts+1);
root[0]=seg.build(0,NN);
for(int i=1;i<=ts;i++){
if(nw[i]!=-1)root[i]=seg.insert(root[i-1],0,NN,nw[i]);
else root[i]=root[i-1];
}
while(q--){
int v,x,k;
cin>>v>>x>>k;
for(int i=25;i>=0;i--){
if(par[v][i]&&w[par[v][i]]<=x)v=par[v][i];
}
int l=dfn[v],r=dfn[v]+siz[v]-1;
int cnt=seg.t[root[r]].cnt-seg.t[root[l-1]].cnt;
if(cnt<k){
cout<<"-1\n";
continue;
}
k=cnt-k+1;
cout<<nums[seg.query(root[l-1],root[r],0,NN,k)]<<"\n";
}
}P1967 [NOIP2013 提高组] 货车运输
题意：
每次询问，求两个节点的最大路径最小
思路：
最大生成树
cpp
struct Edge{
int u,v,w;
bool operator<(const Edge&tmp)const{
return w>tmp.w;
}
};
struct DSU{
vector<int> par;
void init(int n){
par.resize(n,0);
iota(par.begin(),par.end(),0);
}
int find(int x){
return par[x]==x?x:par[x]=find(par[x]);
}
bool merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return false;
par[y]=x;
return true;
}
bool same(int x,int y){
return find(x)==find(y);
}
} dsu;
int idx,n,m,q,w[N],par[N][30],dep[N];
vector<int> adj[N];
vector<Edge> e;
void Ex_kruscal(){
sort(e.begin(),e.end());
dsu.init(2*n+1);
for(auto [u,v,c]:e){
if(dsu.same(u,v))continue;
++idx;
u=dsu.find(u),v=dsu.find(v);
adj[idx].push_back(u);
adj[idx].push_back(v);
dsu.merge(idx,u);
dsu.merge(idx,v);
w[idx]=c;
}
}
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
par[u][0]=fa;
for(int i=1;i<=__lg(dep[u]);i++)par[u][i]=par[par[u][i-1]][i-1];
for(auto v:adj[u])dfs(v,u);
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
while(dep[u]>dep[v]){
u=par[u][(int)__lg(dep[u]-dep[v])];
}
if(u==v)return u;
for(int i=log2(dep[u]);i>=0;i--){
if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
}
return par[u][0];
}
void solve(){
cin>>n>>m;
idx=n;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
e.push_back({u,v,w});
}
Ex_kruscal();
for(int i=1;i<=idx;i++){
if(dsu.find(i)==i)dfs(i,0);
}
cin>>q;
while(q--){
int x,y;
cin>>x>>y;
if(!dsu.same(x,y)){
cout<<"-1\n";
continue;
}
cout<<w[lca(x,y)]<<"\n";
}
}P4768 [NOI2018] 归程
题意：
n个点m条边，每条边有海拔a和边长l，家在点1
如果当前边海拔不高于水位，则只能步行
q次询问，要求在线，每次询问为v p表示当天水位为p，从v出发回家的最小步行距离
思路：
- 先对每个点求一次从1开始的dijkstra
- 建立最大生成树，重构树
- 找出深度最浅的大于等于p的点，那么该点的子树可以任意到达，对子树的点最短距离求min即可
cpp
struct Edge{
int u,v,w;
bool operator<(const Edge&tmp)const{
return w>tmp.w;
}
};
struct DSU{
vector<int> par;
void init(int n){
par.resize(n,0);
iota(par.begin(),par.end(),0);
}
int find(int x){
return par[x]==x?x:par[x]=find(par[x]);
}
bool merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return false;
par[y]=x;
return true;
}
bool same(int x,int y){
return find(x)==find(y);
}
} dsu;
int idx,n,m,q,w[N],dis[N],par[N][30],dep[N],ANS[N];
bool vis[N];
vector<int> adj[N];
vector<PII> g[N];
vector<Edge> e;
void Ex_kruscal(){
sort(e.begin(),e.end());
dsu.init(2*n+1);
for(auto [u,v,c]:e){
if(dsu.same(u,v))continue;
++idx;
u=dsu.find(u),v=dsu.find(v);
adj[idx].push_back(u);
adj[idx].push_back(v);
dsu.merge(idx,u);
dsu.merge(idx,v);
w[idx]=c;
}
}
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
par[u][0]=fa;
for(int i=1;i<=__lg(dep[u]);i++)par[u][i]=par[par[u][i-1]][i-1];
for(auto v:adj[u]){
dfs(v,u);
ANS[u]=min(ANS[u],ANS[v]);
}
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
while(dep[u]>dep[v]){
u=par[u][(int)__lg(dep[u]-dep[v])];
}
if(u==v)return u;
for(int i=log2(dep[u]);i>=0;i--){
if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
}
return par[u][0];
}
void dijk(){
priority_queue<PII,vector<PII>,greater<PII>> q;
for(int i=0;i<=n;i++)dis[i]=1e18,vis[i]=0;
dis[1]=0;
q.push({0,1});
while(!q.empty()){
auto [d,u]=q.top();
q.pop();
if(vis[u])continue;
vis[u]=1;
for(auto [v,c]:g[u]){
if(dis[v]>dis[u]+c){
dis[v]=dis[u]+c;
q.push({dis[v],v});
}
}
}
}
void solve(){
cin>>n>>m;
idx=n;
for(int i=1;i<=m;i++){
int u,v,w,l;
cin>>u>>v>>l>>w;
g[u].push_back({v,l});
g[v].push_back({u,l});
e.push_back({u,v,w});
}
dijk();
Ex_kruscal();
for(int i=0;i<=idx;i++){
ANS[i]=1e18;
if(i<=n)ANS[i]=dis[i];
}
dfs(idx,0);
int ans=0;
int Q,K,S;
cin>>Q>>K>>S;
while(Q--){
int v,p;
cin>>v>>p;
v=(v+K*ans-1)%n+1;
p=(p+K*ans)%(S+1);
for(int i=25;i>=0;i--){
if(par[v][i]&&w[par[v][i]]>p)v=par[v][i];
}
ans=ANS[v];
cout<<ans<<'\n';
}
e.clear();
for(int i=0;i<=idx;i++){
adj[i].clear(),g[i].clear();
w[i]=dis[i]=dep[i]=ANS[i]=vis[i]=0;
for(int j=0;j<30;j++)par[i][j]=0;
}
}AGC002D
题意：
n个点m条边，每次询问x y z表示从x和y出发经过z个点，边的最大编号最小
思路：
- 最小生成树重构树
- 每次二分答案
- 那么上界就有了，直接往上跳
- 注意x和y如果跳到同一个点只算一次
cpp
struct Edge{
int u,v,w;
bool operator<(const Edge&tmp)const{
return w<tmp.w;
}
};
struct DSU{
vector<int> par;
void init(int n){
par.resize(n,0);
iota(par.begin(),par.end(),0);
}
int find(int x){
return par[x]==x?x:par[x]=find(par[x]);
}
bool merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return false;
par[y]=x;
return true;
}
bool same(int x,int y){
return find(x)==find(y);
}
} dsu;
int idx,n,m,q,w[N],par[N][30],dep[N],sum[N];
bool vis[N];
vector<int> adj[N];
vector<PII> g[N];
vector<Edge> e;
void Ex_kruscal(){
sort(e.begin(),e.end());
dsu.init(2*n+1);
for(auto [u,v,c]:e){
if(dsu.same(u,v))continue;
++idx;
u=dsu.find(u),v=dsu.find(v);
adj[idx].push_back(u);
adj[idx].push_back(v);
dsu.merge(idx,u);
dsu.merge(idx,v);
w[idx]=c;
}
}
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
par[u][0]=fa;
for(int i=1;i<=__lg(dep[u]);i++)par[u][i]=par[par[u][i-1]][i-1];
for(auto v:adj[u])dfs(v,u),sum[u]+=sum[v];
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
while(dep[u]>dep[v]){
u=par[u][(int)__lg(dep[u]-dep[v])];
}
if(u==v)return u;
for(int i=log2(dep[u]);i>=0;i--){
if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
}
return par[u][0];
}
bool check(int mid,int x,int y,int z){
for(int i=25;i>=0;i--){
if(par[x][i]&&w[par[x][i]]<=mid)x=par[x][i];
if(par[y][i]&&w[par[y][i]]<=mid)y=par[y][i];
}
if(x==y)return sum[x]>=z;
return sum[x]+sum[y]>=z;
}
void solve(){
cin>>n>>m;
idx=n;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
e.push_back({u,v,i});
}
Ex_kruscal();
for(int i=1;i<=n;i++)sum[i]=1;
dfs(idx,0);
int q;
cin>>q;
while(q--){
int x,y,z;
cin>>x>>y>>z;
int l=1,r=m;
while(l<r){
int mid=l+r>>1;
if(check(mid,x,y,z))r=mid;
else l=mid+1;
}
cout<<l<<"\n";
}
}