建图
kruskal重构树是个啥？
故名思意就是在跑kruskal的过程中重构出的一颗树
对于kruskal跑生成树时加进去的一条边(u,v)
我们在重构树中建立一个新节点t，连边(t,rt[u]),(t,rt[v])
t成为rt[u],rt[v]的父亲，rt[x]表示x在重构树中暂时的根节点(最后根节点都一样了嘛)
性质
- kruskal重构树是一颗二叉树
- 跑最小生成树形成的kruskal重构树是个大根堆
- 所有原图中的点在重构树中都是叶子节点
- 任意两点路径上边权的最大值为它们LCA的点权
货车运输
建立最大生成树，然后建这颗生成树的kruskal重构树
显然先用并查集判断两点是否联通，再直接拿重构树上两点lca的权值即路径中的最小权值
#include<bits/stdc++.h>
using namespace std;
const int maxn=10005,maxm=50005;
struct edge{
int x,y,z;
bool operator <(edge i)const{
return z>i.z;
}
}ed[maxm];
struct Edge{
int to;
int nxt;
}e[4*maxn];
int cnt;
int head[2*maxn];
int fat[2*maxn];
int val[2*maxn];
int dep[2*maxn],f[2*maxn][21];
bool vis[2*maxn];
int read(){
int x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*y;
}
int find(int x){
if(fat[x]==x)return x;
return fat[x]=find(fat[x]);
}
void add(int u,int v){
e[cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt++;
return ;
}
void dfs(int x,int fa){
dep[x]=dep[fa]+1;
f[x][0]=fa;
for(int i=1;i<=20;i++)
f[x][i]=f[f[x][i-1]][i-1];
for(int i=head[x];i!=-1;i=e[i].nxt){
int tmp=e[i].to;
if(tmp==fa)continue;
dfs(tmp,x);
}
return ;
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;i--)
if(dep[f[x][i]]>=dep[y])
x=f[x][i];
if(x==y)return x;
for(int i=20;i>=0;i--)
if(f[x][i]!=f[y][i]){
x=f[x][i];
y=f[y][i];
}
return f[x][0];
}
int main(){
int n,m,q;
n=read();m=read();
for(int i=1;i<=2*n;i++)fat[i]=i;
for(int i=1;i<=m;i++){
int x,y,z;
x=read();y=read();z=read();
ed[i].x=x;ed[i].y=y;ed[i].z=z;
}
sort(ed+1,ed+m+1);
int es=n;
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++){
int u=ed[i].x,v=ed[i].y,w=ed[i].z;
if(find(u)==find(v))continue;
es++;
val[es]=w;
add(es,find(u));
add(es,find(v));
fat[find(u)]=fat[find(v)]=es;
}
for(int i=1;i<=n;i++){
if(vis[find(i)])continue;
vis[find(i)]=1;
dfs(find(i),0);
}
q=read();
for(int i=1;i<=q;i++){
int x,y;
x=read();y=read();
if(find(x)!=find(y)){
printf("-1\n");
continue;
}
printf("%d\n",val[lca(x,y)]);
}
return 0;
}
Peaks
考虑建一颗最小生成树的重构树
建下来后，我们想找到所有v能到达的山峰中第k高的
所有v能到达的山峰一定在v的某一级祖先的整棵子树里
那一级祖先满足的条件应是再上一级祖先的权值大于x
对于这一颗子树我们需要找第k大的点
考虑主席树，先将原重构树dfs序，然后子树一定在一个区间里
建立主席树，查询区间第k大
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=100005,maxm=500005,inf=0x3f3f3f3f;
struct node{
int ls,rs;
int num;
}tree[20*2*maxn];
int cur;
int root[2*maxn];
struct mountain{
int id;
int h;
bool operator <(mountain i)const{
return h<i.h;
}
}a[maxn];
struct edge{
int a,b,c;
bool operator <(edge i)const{
return c<i.c;
}
}ed[maxm];
struct Edge{
int to;
int nxt;
}e[2*maxn];
int cnt;
int head[2*maxn];
int n,m,q,h;
int high[maxn];
int data[maxn];
int d[2*maxn];
int f[2*maxn];
int dfsnum=0;
int dfn[2*maxn];
int son[2*maxn];
int pre[2*maxn][21];
bool vis[2*maxn];
int read(){
int x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*y;
}
int find(int x){
if(f[x]==x)return x;
return f[x]=find(f[x]);
}
void add(int u,int v){
e[cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt++;
return ;
}
void modify(int x,int y,int l,int r,int val){
if(l==r){
tree[x].ls=tree[y].rs=0;
tree[x].num=tree[y].num+1;
return ;
}
int mid=l+((r-l)>>1);
tree[x].num=tree[y].num+1;
if(val<=mid){
tree[x].ls=++cur;
tree[x].rs=tree[y].rs;
modify(tree[x].ls,tree[y].ls,l,mid,val);
}
else{
tree[x].rs=++cur;
tree[x].ls=tree[y].ls;
modify(tree[x].rs,tree[y].rs,mid+1,r,val);
}
return ;
}
int query(int x,int y,int l,int r,int k){
if(l==r)return data[l];
int mid=l+((r-l)>>1);
int ls1=tree[x].ls,rs1=tree[x].rs;
int ls2=tree[y].ls,rs2=tree[y].rs;
int num=tree[rs2].num-tree[rs1].num;
if(tree[y].num-tree[x].num<k)return -1;
if(num>=k)
return query(rs1,rs2,mid+1,r,k);
else
return query(ls1,ls2,l,mid,k-num);
}
void dfs(int x,int fa){
dfn[x]=++dfsnum;
root[dfn[x]]=root[dfn[x]-1];
if(x<=n){
root[dfn[x]]=++cur;
modify(root[dfn[x]],root[dfn[x]-1],1,h,high[x]);
}
son[x]=1;
pre[x][0]=fa;
for(int i=1;i<=20;i++)
pre[x][i]=pre[pre[x][i-1]][i-1];
for(int i=head[x];i!=-1;i=e[i].nxt){
int tmp=e[i].to;
dfs(tmp,x);
son[x]+=son[tmp];
}
return ;
}
signed main(){
n=read();m=read();q=read();
for(int i=1;i<=n;i++){a[i].id=i;a[i].h=read();}
sort(a+1,a+n+1);
high[a[1].id]=++h;
data[h]=a[1].h;
for(int i=2;i<=n;i++){
if(a[i].h>a[i-1].h)data[++h]=a[i].h;
high[a[i].id]=h;
}
for(int i=1;i<=m;i++){
int a,b,c;
a=read();b=read();c=read();
ed[i].a=a;ed[i].b=b;ed[i].c=c;
}
sort(ed+1,ed+m+1);
int tot=n;
for(int i=1;i<=2*n;i++)f[i]=i;
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++){
int u=ed[i].a,v=ed[i].b,w=ed[i].c;
u=find(u);
v=find(v);
if(u==v)continue;
tot++;
d[tot]=w;
f[u]=f[v]=tot;
add(tot,u);
add(tot,v);
}
tree[0].ls=tree[0].rs=tree[0].num=0;
for(int i=1;i<=tot;i++){
if(vis[find(i)])continue;
vis[find(i)]=1;
dfs(find(i),0);
}
for(int i=1;i<=q;i++){
int v,x,k;
v=read();x=read();k=read();
for(int j=20;j>=0;j--)
if(pre[v][j]&&d[pre[v][j]]<=x)
v=pre[v][j];
printf("%lld\n",query(root[dfn[v]-1],root[dfn[v]+son[v]-1],1,h,k));
}
return 0;
}
[NOI2018]归程
这里我们对于每一个询问只能用单车跑海拔大于p的边，我们需要在所有能走这些边到达的点i中dis[i]最小的值
disi[i]表示从1到i的最短路
显然想到kruskal重构树
建立好最大生成树的重构树后，v点能去的点就是它的某级祖先的整棵子树里的所有点
这个祖先满足再上以及祖先的点权小于p
那么我们需要这一整棵子树的最小dis值
来一遍树形dp即能得到答案
#include<bits/stdc++.h>
using namespace std;
const int maxn=200005,maxm=400005;
const long long inf=0x3f3f3f3f3f3f3f3f;
struct edge{
int u,v,a;
bool operator <(edge i)const{
return a>i.a;
}
}ed[maxm];
struct que{
int id;
long long data;
bool operator <(que i)const{
return data>i.data;
}
};
struct Edge{
int to;
long long w;
int nxt;
}e[2*maxm];
int cnt;
int head[2*maxn];
int n,m;
int f[2*maxn];
long long dis[2*maxn];
long long val[2*maxn],dp[2*maxn];
int pre[2*maxn][21];
bool vis[2*maxn];
priority_queue<que>q;
int read(){
int x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*y;
}
void add(int u,int v,long long w){
e[cnt].to=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt++;
return ;
}
void dijkstra(){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
que u;
u.id=1;u.data=0;dis[1]=0;
q.push(u);
while(!q.empty()){
int k=q.top().id;
q.pop();
if(vis[k])continue;
vis[k]=1;
for(int i=head[k];i!=-1;i=e[i].nxt){
int tmp=e[i].to;
if(dis[tmp]<=dis[k]+e[i].w)continue;
dis[tmp]=dis[k]+e[i].w;
que o;
o.id=tmp;o.data=dis[tmp];
q.push(o);
}
}
return ;
}
int find(int x){
if(f[x]==x)return x;
return f[x]=find(f[x]);
}
void dfs(int x,int fa){
// cout<<"ORZ"<<fa<<" "<<n<<endl;
pre[x][0]=fa;
for(int i=1;i<=20;i++)
pre[x][i]=pre[pre[x][i-1]][i-1];
if(x<=n)dp[x]=dis[x];
else dp[x]=inf;
for(int i=head[x];i!=-1;i=e[i].nxt){
int tmp=e[i].to;
dfs(tmp,x);
dp[x]=min(dp[x],dp[tmp]);
}
return ;
}
int main(){
int t;
t=read();
while(t--){
n=read();m=read();
cnt=0;
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++){
int u,v,l,a;
u=read();v=read();l=read();a=read();
add(u,v,l);
add(v,u,l);
ed[i].u=u;ed[i].v=v;ed[i].a=a;
}
dijkstra();
cnt=0;
memset(head,-1,sizeof(head));
sort(ed+1,ed+m+1);
int tot=n;
for(int i=1;i<=2*n;i++)f[i]=i;
for(int i=0;i<=n;i++)val[i]=0;
for(int i=1;i<=m;i++){
int u=ed[i].u,v=ed[i].v,a=ed[i].a;
if(find(u)==find(v))continue;
tot++;
val[tot]=a;
add(tot,find(u),0);
add(tot,find(v),0);
f[find(u)]=f[find(v)]=tot;
}
memset(vis,0,sizeof(vis));
for(int i=1;i<=tot;i++){
if(vis[find(i)])continue;
vis[find(i)]=1;
dfs(find(i),0);
}
int lastans=0;
int Q,K,S;
Q=read();K=read();S=read();
for(int i=1;i<=Q;i++){
int v,p;
v=(read()+K*lastans-1)%n+1;
p=(read()+K*lastans)%(S+1);
for(int j=20;j>=0;j--)
if(val[pre[v][j]]>p)
v=pre[v][j];
// cout<<"**"<<val[v]<<" "<<p<<endl;
lastans=dp[v];
printf("%lld\n",dp[v]);
}
}
return 0;
}
