首页 > 代码库 > 51nod 1513 && CF570D
51nod 1513 && CF570D
题意:给定一棵树,每个节点有一个字母。给定若干个询问,询问某个子树内某一深度的节点是否能将这些节点组合成一个回文串。(深度是以根节点为基准的,不是当前子树根。)数据规模10^5。
神犇题解
子树问题,一般都是dfs序。这道题我们把所有节点分类:f[i][j]表示i深度j字母,然后把这一类节点按照dfs序压进去。
对于一个询问只要把在它dfs序管辖区间(也就是子树内)的节点拿来判断就可以了。
复杂度O(26*nlogn)。
51nod 1513 && CF570D
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。