题意有一个包含n1n1n1个词的词库其中编号为000的单词是空串编号为iii的单词是在编号为pip_ipi​的单词后面加一个字母得到的保证词库中所有单词不重复。Bessie 按照一定顺序读出不是任何单词的前缀的单词依次读的单词的编号在输入中用wiw_iwi​表示。Bessie 念一个单词的时候是一个一个字母读的当读完一个字母后可以确认这个单词是哪一个的时候Elsie 就会让她停下问每个单词要读几个字母。分析先举个例子找找思路。题目中有要求piip_iipi​i但是例子是我随手画的不影响思路分析又懒得再画一个了所以与题目要求不符此处致歉15 0 0 12 1 4 4 5 5 5 2 2 10 11 11 12可以根据条件画出一棵树来表示每个节点的父亲为pip_ipi​类似于 trie当然你不知道 trie 也没事不影响父节点加上一个字母就会变成子节点可以发现每个点所处的深度就是单词的长度000号节点深度为000。什么样的单词会被读出来不是任何单词的前缀的单词就是这棵树上的叶子节点。假设我们第一个单词读了555号我们发现要读三个字母因为555的父亲444有两个孩子不读到最后一个字母就不知道到底是哪个单词。此时555号读过了我们把它删掉。现在我们依次读单词7, 8, 97,\,8,\,97,8,9。777和888都需要读到最后一个字母即第444个我们再把777和888删掉。读999号的时候我们发现只要读出一个字母我们就知道单词一定在111号节点为根的子树内其他叶子节点和单词999没有公共前缀。如果你觉得还是没有发现规律那我们就继续读。999读了之后以111为根的子树内已经没有能读的单词了可以全部砍掉。接下来读151515必须要从000开始向下走444步才能确定单词151515把151515删去后读单词333。读了两个字母后可以确定单词在101010为根的子树内101010为根的子树内只剩333这一个单词了所以只用读两个字母。发现规律每次一个子树内没有可读单词的时候这个子树应被删除若从某个节点往下走每个节点都只有一个儿子则必能确定一个单词所以我们可以从一个单词往上走只能走儿子数量为111的节点最终走到的点的深度就是需要读的字母数。简单解释一下第一条当所有除了141414的单词都被读过之后就不需要读任何字母也能确定单词了若没有把以111为根的子树删除则000会有两个儿子无法从222走到000会判定需要读一个字母来确定单词在222的子树里。时间复杂度是O(n)O(n)O(n)因为往上走的时候每个节点只会经过一次走过之后都会删除。实现从一个点xxx开始反复执行xfa[x]直到son[fa[x]]1为止输出dep[x]将xxx为根的子树删除son[fa[x]]--。这里非常不建议用dfs我莫名其妙被卡了时间复杂度换成从111到nnn枚举就不超时了父亲的编号一定小于孩子所以可以从小到大处理。#includebits/stdc.husingnamespacestd;intn,p[1000005],w,son[1000005],dep[1000005];intmain(){cinn;p[0]-1;for(inti1;in;i){scanf(%d,p[i]);dep[i]dep[p[i]]1;son[p[i]];}while(scanf(%d,w)){inttw;while(1){if(p[t]-1)break;if(son[p[t]]!1)break;tp[t];}if(t0){printf(0\n);break;}elseprintf(%d\n,dep[t]);son[p[t]]--;}return0;}