怎么联系网站开发团队,wordpress 微博小工具,中文wordpress网站模板,wordpress通过关键词题干#xff1a;
H公司一共有N名员工#xff0c;编号为1~N#xff0c;其中CEO的编号是1。除了CEO之外#xff0c;每名员工都恰好有唯一的直接上司#xff1b;N名员工形成了一个树形结构。
我们定义X的1级上司是他的直接上司#xff0c;2级上司是他上司的上司#xf…题干
H公司一共有N名员工编号为1~N其中CEO的编号是1。除了CEO之外每名员工都恰好有唯一的直接上司N名员工形成了一个树形结构。
我们定义X的1级上司是他的直接上司2级上司是他上司的上司以此类推……
请你找出每名员工的D级上司是谁。
Input
第一行包含2个整数N和D。
以下N-1行每行包含一个整数依次代表编号是2-N的员工的直接上司的编号。
对于50%的数据1 ≤ N, D ≤ 10000
对于100%的数据1 ≤ N, D ≤ 100000
Output
依次输出1~N的D级上司的编号每个一行。如果某员工没有D级上司输出-1。
Sample Input
5 2
1
1
3
3
Sample Output
-1
-1
-1
1
1
解题报告 开一个数组记录dfs的过程中走过的节点跟走迷宫差不多啊只不过网格图换成了树形图。。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
vectorint vv[MAX];
int n,d;
int ans[MAX],dep[MAX];
void dfs(int cur,int root,int deep) {dep[deep] cur;if(deep - d 0) ans[cur] dep[deep-d];int up vv[cur].size();for(int i 0; iup; i) {int v vv[cur][i];if(v root) continue;dfs(v,cur,deep1);}
}
int main()
{memset(ans,-1,sizeof ans);cinnd;for(int i 2,x; in; i) {scanf(%d,x);vv[x].pb(i);vv[i].pb(x);}dfs(1,-1,0);for(int i 1; in; i) {printf(%d\n,ans[i]);} return 0 ;}
总结 这题其实应该加单向边但是双向边也可以AC我感觉原因就在于是个树形图又因为是从根节点开始搜的所以每次搜到的边都是上级搜到下级的边这可以算是个树形图的一个小结论了其实也很常用因为貌似所有的树形图都可以这样去使用双向边貌似还没出过错。
