题目 题意: 给定n个节点的树，以1为根。规定dfs时优先搜索编号小的点，而且给出边的顺序也按从小到大给的。给定m次询问，O(1)求出以u为树根进行dfs的第k个数。 思路: 感觉和以前打的一场abc的E有点像，但是不太会写，乱写了一个T了，然后一直思绪乱乱的，直接罚坐了，200多人过的题都不会，确实不应该。 从树根开始搜和从u开始是一样的，所以从树根搜一遍得到的序列就可以O(1)查询。那么怎么记录呢?dfs序的第i个数对应出现次序为i，u的出现次序+k-1即以u为树根进行dfs的第k个数。如果以u为树根的子树大小n>>m; for(int i=2;i>x; va[x].push_back(i); } dfs(1); for(int i=0;i
关注
打赏
查看更多评论
