C - 小睿睿的兄弟
题目大意(划重点)
- 有一棵树,肯定要跑一遍啊
- 求x的第k代兄弟,说明他肯定要有这个祖先而且兄弟得有这么多
- 还要求k小值(giao),怎么这么麻烦
分析问题(现在没有探讨珂学)
首先得有一个全局思想(我要求什么,怎么求)
我们要求一个k祖先,所以记录一个数组f[i][j],表示点j的(1<<i)代祖先
解决这个问题的关键一步,是想出怎么求出x的兄弟,因为他们虽然可能在同一层,但是有可能没有共同的k代祖先
但是可以发现,如果我们以深度为第一关键字,遍历顺序为第二关键字,开一个vector存储每一个深度对应的节点,就可以保证这些节点的有序,所以还要在遍历树时建立一个时间戳,就像这样
可以发现的是,只要对于某个x的第k代祖先,我们在时间戳为dfn[k]~dfn[k]+siz[k]-1的范围内寻找就不会找到在其他子树上处于同一深度的节点然后就是k小值,难道是暴力枚举,然后sort排序?怎么可能,我们可以以深度为序,对每个点建立一棵树(主席树),不会的话可以去敲敲模板
代码
- 我们分开放
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int n,m,tot,cnt,idx,scc; int h[N],nex[N<<1],ver[N<<1],val[N]; int dfn[N],dep[N],siz[N],f[20][N]; int lc[N],rc[N],rt[N],id[N],s[N]; vector<int>t[N]; //记录深度为i的点有多少个 /*********跑图部分*********/ inline int god(int x,int y) { if(dep[x]==dep[y]) return dfn[x]<dfn[y]; return dep[x]<dep[y]; } inline void add(int x,int y) { nex[tot]=h[x]; ver[tot]=y; h[x]=tot++; } inline void dfs(int u,int v) { siz[u]=1;dep[u]=dep[v]+1; f[0][u]=v;dfn[u]=++idx; //时间戳记顺序 for (int i=1;i<=18;i++) f[i][u]=f[i-1][f[i-1][u]]; for (int i=h[u];~i;i=nex[i]) { int j=ver[i]; if(j==v) continue; dfs(j,u); siz[u]+=siz[j]; } }//dfs跑节点 inline int lca(int k,int x) { for (int i=20;i>=0;i--) if(k&(1<<i)) x=f[i][x]; return x; }//求出祖先 /*******建树部分*********/ inline void build(int l,int r,int &now) { now=++scc; s[now]=0; if(l==r) return ; int mid=(l+r)>>1; build(l,mid,lc[now]);build(mid+1,r,rc[now]); } inline void ins(int l,int r,int las,int &pas,int x) { pas=++scc; lc[pas]=lc[las];rc[pas]=rc[las]; s[pas]=s[las]+1; if(l==r) return ; int mid=(l+r)>>1; if(x<=mid) ins(l,mid,lc[las],lc[pas],x); else ins(mid+1,r,rc[las],rc[pas],x); }/*插入新值*/ inline int ask(int l,int r,int x,int y,int k) { if(l==r) return l; int sum=s[lc[y]]-s[lc[x]]; int mid=(l+r)>>1; if(sum<k) return ask(mid+1,r,rc[x],rc[y],k-sum); else return ask(l,mid,lc[x],lc[y],k); }//经典的区间求k小值 inline void pre() { for (int i=1;i<=n;i++) rt[i]=i; sort(rt+1,rt+n+1,god); //排序原因 :拥有同一个k祖先的是一群连续的点 for (int i=1;i<=n;i++) t[dep[rt[i]]].push_back(rt[i]); //记录每个深度的节点 int max_dep=0; for (int i=1;i<=n;i++) max_dep=max(max_dep,dep[i]); build(1,n,rt[0]);//建立初始的树 for (int i=1;i<=max_dep;i++) { int len=t[i].size(); for (int j=0;j<len;j++) { int p=t[i][j]; id[p]=++cnt; ins(1,n,rt[cnt-1],rt[cnt],val[p]); } } } int main() { memset(h,-1,sizeof(h)); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&val[i]); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y);add(y,x); } dfs(1,0);pre(); int las=0; while(m--) { int x,y; scanf("%d%d",&x,&y);x=(x^las)%n+1; if(dep[x]<=y) { puts("?"); continue; } int op=lca(y,x); int lk=0,rk=0; int lm=dfn[op],rm=dfn[op]+siz[op]-1,now=dep[op]+y; int l=0,r=t[now].size()-1; while(l<=r) { int uo=(l+r)>>1; int mid=dfn[t[now][uo]]; if(mid<lm) l=uo+1; else lk=t[now][uo],r=uo-1; } l=0,r=t[now].size()-1; while(l<=r) { int uo=(l+r)>>1; int mid=dfn[t[now][uo]]; if(mid>rm) r=uo-1; else rk=t[now][uo],l=uo+1; }//二分两次,找到对应的区间 if(id[rk]-id[lk]+1<y) { puts("?"); continue; } las=ask(1,n,rt[id[lk]-1],rt[id[rk]],y); printf("%d\n",las); } return 0; }
后话
- 当时比赛结束,去网上搜题解时,发现只有一个,还是个错的(别问我为什么知道),然后决定自己打,先是调试,再是码字,但是结束后一身轻松,很爽(QwQ),但是可能有一些地方是口胡的,如果有问题,还请指出,Thanks♪(・ω・)ノ