正題

題目鏈接:https://www.luogu.com.cn/problem/P4197

---

題目大意

$n$個點的一張無向圖，每個點有一個$h_i$，邊有權值。

$q$次詢問從$v$出發(fā)不走權值超過$x$的路徑能到達的第$k$大$h_i$是多少。

---

解題思路

構一顆$Kruskal$重構樹之后就變成了求子樹中第$k$大的值是多少了，用$Kruskal$重構樹上的$dfs$序建立一棵主席樹就好了。

時間復雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=5e5+10,T=20; struct Seq_Tree{int cnt,val[N<<3],ls[N<<3],rs[N<<3];int Change(int x,int l,int r,int pos){int now=++cnt;val[now]=val[x]+1;if(l==r)return now;int mid=(l+r)>>1;if(pos<=mid)ls[now]=Change(ls[x],l,mid,pos),rs[now]=rs[x];else rs[now]=Change(rs[x],mid+1,r,pos),ls[now]=ls[x];return now;}int Ask(int x,int y,int l,int r,int k){if(l==r)return l;int mid=(l+r)>>1,w=val[rs[y]]-val[rs[x]];if(k<=w)return Ask(rs[x],rs[y],mid+1,r,k);return Ask(ls[x],ls[y],l,mid,k-w);} }Tr; struct node{int x,y,w; }e[N]; struct edge_node{int to,next; }a[N*2]; int n,m,q,tot,cnt,h[N],b[N],ls[N],fa[N],val[N]; int rt[N],dfn[N],rfn[N],ed[N],f[N][T+1]; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } bool cmp(node x,node y) {return x.w<y.w;} int find(int x) {return (fa[x]==x)?(x):(fa[x]=find(fa[x]));} void dfs(int x,int fa){dfn[++cnt]=x;rfn[x]=cnt;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;f[y][0]=x;dfs(y,x);}ed[x]=cnt;return; } int ck(int x,int w){for(int i=T;i>=0;i--)if(val[f[x][i]]<=w)x=f[x][i];return x; } int main() {scanf("%d%d%d",&n,&m,&q);for(int i=1;i<=n;i++)scanf("%d",&h[i]),b[i]=h[i];sort(b+1,b+1+n);int num=unique(b+1,b+1+n)-b-1;for(int i=1;i<=n;i++)h[i]=lower_bound(b+1,b+1+num,h[i])-b;for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);for(int i=1;i<=n+m;i++)fa[i]=i;sort(e+1,e+1+m,cmp);cnt=n;for(int i=1;i<=m;i++){int Fa=find(e[i].x),Fb=find(e[i].y);if(Fa==Fb)continue;val[++cnt]=e[i].w;addl(cnt,Fa);addl(cnt,Fb);fa[Fa]=fa[Fb]=fa[cnt];}cnt=0;val[0]=2147483647;b[0]=-1;for(int i=1;i<=n;i++)if(!rfn[find(i)])dfs(find(i),0);for(int i=1;i<=cnt;i++)rt[i]=Tr.Change(rt[i-1],0,num,h[dfn[i]]);for(int j=1;j<=T;j++)for(int i=1;i<=cnt;i++)f[i][j]=f[f[i][j-1]][j-1];while(q--){int x,w,k;scanf("%d%d%d",&x,&w,&k);x=ck(x,w);printf("%d\n",b[Tr.Ask(rt[rfn[x]-1],rt[ed[x]],0,num,k)]);}return 0; }

總結

以上是生活随笔為你收集整理的P4197-Peaks【Kruskal重构树,主席树】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。