美团笔试0903，字母树思路，暴力解。
for循环暴力过，700+ms；
思路：从后向前遍历，每次再做一个循环遍历i到n，查找子节点（查看其父节点是否为本节点），然后查询子节点的桶，来构造本节点的桶，最后遍历本节点的桶计算字符数；
#include <stdio.h>
#include <stdlib.h>
int main(){
int num,i=0;
unsigned short int dadnode[50001];
char node[50001];
scanf("%d",&num);
while(i<num-1)
scanf("%d ",dadnode+i++);
i=0;
while(i<num)
scanf("%c",node+i++);
char ans[50001] = {0};
char arr[50001][26] = {0}; // 给每个节点分配一个桶；
for(i=num-1;i>=0;i--){
arr[i][node[i]-'A']++; // 本身是个节点，至少有一个字符；
for(int j=i;j<num-1;j++){ // 查看后续节点是否为子节点；
if(dadnode[j] == i+1){
for(int k=0;k<26;k++){
if(arr[j+1][k]) // 根据子节点的桶构造本节点的桶；
arr[i][k]++;
}
}
}
for(int k=0;k<26;k++){ // 遍历桶计算无重复字符数；
if(arr[i][k])
ans[i]++;
}
}
for(i=0;i<num;i++){
printf("%d ",ans[i]);
}
return 0;
} 
投递快手等公司10个岗位 >
