打卡信奥刷题（3088）用C++实现信奥题 P7103 「C.E.L.U-01」族谱树

P7103 「C.E.L.U-01」族谱树题目背景小 Soup 正在翻看他们家的族谱他们家的族谱构成了一棵树。小 Soup 发现由于年代久远他们家族中的一些分支已经绝迹他对此十分好奇。题目描述小 Soup 给你他们家的族谱树想要问你在这棵树中所有第kkk层的孩子树中深度为kkk的点根节点的深度为111,根节点编号为111的最近公共祖先\text{最近公共祖先}最近公共祖先是谁。输入格式第一行两个整数n,mn,mn,m。第二行nnn个整数其中第iii个整数为fif_ifi​表示iii的父亲为fif_ifi​请注意111的fif_ifi​固定为000。接下来mmm行每行一个整数kkk代表小 Soup 的询问。输出格式对于每个小 Soup 的询问输出一个整数即所有深度为kkk的点的最近公共祖先\text{最近公共祖先}最近公共祖先。输入输出样例 #1输入 #18 3 0 1 1 2 2 3 4 5 2 1 4输出 #11 1 2输入输出样例 #2输入 #211 4 0 1 1 3 3 3 4 5 8 8 10 3 4 5 6输出 #23 3 8 11说明/提示样例解释1样例解释2数据保证存在深度为kkk的点数据编号n,m特殊性质1≤10╲2≤100╲3∼4≤103╲5≤3×105树为一条链6≤3×105╲7∼10≤3×106╲11∼12≤5×106╲\begin{array}{|c|c|c|}数据编号n,m特殊性质\\1\le10\diagdown\\2\le100\diagdown\\3\sim4\le10^3\diagdown\\5\le3\times10^5树为一条链\\6\le3\times10^5\diagdown\\7\sim10\le3\times10^6\diagdown\\11\sim12\le5\times10^6\diagdown\end{array}数据编号123∼4567∼1011∼12​n,m≤10≤100≤103≤3×105≤3×105≤3×106≤5×106​特殊性质╲╲╲树为一条链╲╲╲​对于100%100\%100%的数据n≤5×106,m≤nn\le5\times10^6,m\le nn≤5×106,m≤n。温馨提示此题较卡常请注意大常数带来的影响以及时空复杂度。如果你被卡常了可以试试使用快速读入。C实现#includebits/stdc.h#defineRregisterintusingnamespacestd;constintN5e65;intn,d[N],to[N],nx[N],h[N],fa[N],q,in,ans[N];inlineintread()//快读就不用说了吧{ints0;charcgetchar();while(!isdigit(c))cgetchar();while(isdigit(c))s(s3)(s1)(c^48),cgetchar();returns;}intfind(intp){returnfa[p]p?p:fa[p]find(fa[p]);}//并查集voiddfs(intx,intf){d[x]d[f]1;for(R ih[x];i;inx[i])dfs(to[i],x),fa[to[i]]x;//tarjan 求LCA的合并ans[d[x]]ans[d[x]]?find(ans[d[x]]):x;//核心部分tarjan求LCA中的求答案部分}intmain(){nread();qread();for(R i1;in;i)fa[i]i,inread(),to[i]i,nx[i]h[in],h[in]i;//读入加边并查集initdfs(1,0);while(q--)printf(%d\n,ans[read()]);//O(1) 处理询问return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容