做借贷网站平台,网站建设中心联系方式,wordpress 有缓存吗,北京网络公司网站传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一张图#xff0c;有nnn个山峰#xff0c;每个山峰高度为hih_ihi#xff0c;有mmm条边#xff0c;每条边有个难度值wiw_iwi#xff0c;现在有qqq个询问#xff0c;每次询问给定一个山峰vvv思路题意
给你一张图有nnn个山峰每个山峰高度为hih_ihi有mmm条边每条边有个难度值wiw_iwi现在有qqq个询问每次询问给定一个山峰vvv问从这个山峰开始走经过难度不超过xxx的路径能走到的山峰中第kkk大的山峰高度是多少。 n≤1e5,m,q≤5e5,hi,wi1e9n\le1e5,m,q\le5e5,h_i,w_i1e9n≤1e5,m,q≤5e5,hi,wi1e9
思路
KruskalKruskalKruskal重构树维护连通性经典题啦把边从小到大排序让后建重构树这样每两个点之间的最大路径是他们的lcalcalca的点权那么我们从vvv这个点往上跳一直跳到深度最小的且valf≤xval_f\le xvalf≤x的点让后这颗子树中所有叶子节点就是能到的山峰找第kkk大的问题当然是留给主席树解决啦按照dfsdfsdfs序建主席树查询第kkk大就好了。
//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N200010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m,q;
int a[N],p[N],fa[N][22],in[N],ed[N],se[N],tot;
int root[N],idx,h[N];
vectorintv[N],li;
struct Edge
{int a,b,w;bool operator (const Edge W) const{return wW.w;}
}edge[N*3];
struct Node
{int l,r;int cnt;
}tr[N*40];int find(int x)
{return xp[x]? x:p[x]find(p[x]);
}int get(int x)
{return lower_bound(li.begin(),li.end(),x)-li.begin();
}void insert(int p,int q,int l,int r,int pos)
{qidx; tr[q]tr[p];tr[q].cnt;if(lr) return;int mid(lr)1;if(posmid) insert(tr[p].l,tr[q].l,l,mid,pos);else insert(tr[p].r,tr[q].r,mid1,r,pos);
}int query(int p,int q,int l,int r,int k)
{if(lr) return li[l];int mid(lr)1,cnttr[tr[q].l].cnt-tr[tr[p].l].cnt;if(kcnt) return query(tr[p].l,tr[q].l,l,mid,k);else return query(tr[p].r,tr[q].r,mid1,r,k-cnt);
}void dfs(int u,int f)
{se[u]1;in[u]tot; fa[u][0]f;for(int i1;i19;i) fa[u][i]fa[fa[u][i-1]][i-1];if(un) insert(root[tot-1],root[tot],0,li.size()-1,get(a[u]));else root[tot]root[tot-1];for(auto x:v[u]) if(x!f) dfs(x,u),se[u]se[x];ed[u]tot;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d%d,n,m,q);for(int i1;in;i) scanf(%d,a[i]),li.pb(a[i]);sort(li.begin(),li.end()); li.erase(unique(li.begin(),li.end()),li.end());for(int i1;in*2;i) p[i]i;for(int i1;im;i){int a,b,w; scanf(%d%d%d,a,b,w);edge[i]{a,b,w};}sort(edge1,edge1m);for(int i1,totn;im;i){int aaedge[i].a,bedge[i].b,wedge[i].w;int pafind(aa),pbfind(b);if(papb) continue;tot; p[pa]tot; p[pb]tot;v[tot].pb(pa); v[tot].pb(pb);a[tot]w;if(totn*2-1) break;//coutpa pb tot wendl;}a[0]INF;for(int i1;in*2-1;i) if(ifind(i)) dfs(i,0);int ans0;while(q--){int v,x,k; scanf(%d%d%d,v,x,k);v^ans; x^ans; k^ans; for(int i19;i0;i--) if(a[fa[v][i]]x) vfa[v][i];int sumtr[root[ed[v]]].cnt-tr[root[in[v]-1]].cnt;if(ksum) ans-1;else ansquery(root[in[v]-1],root[ed[v]],0,li.size()-1,sum-k1);printf(%d\n,ans);ansans-1? 0:ans;}return 0;
}
/**/
