坑啊，没这个节点也算回文也要输出 Yes
貌似没见着用重链剖分的写的，于是就来写一波
按照套路设 $ f[i][j][k] $ 表示 $ i $ 的子树内深度为 j 的字母 k 的个数
然后判断能否有回文只需看是否有两个及以上的字母出现次数为奇数次即可
另外像上面那样开数组的话用指针估计有点难受，建议 j,k 压成一维
一定不要想我作死先判断不合法的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| #include<touwenjian.h>
using namespace std;
const int maxn=500500;
int *f[maxn],tmp[maxn*30],*st=tmp;
int n,m,head[maxn],vnum[maxn];
int size,son[maxn],dis[maxn],ans[maxn];
int ls[maxn];
vector <pair<int,int> > q[maxn];
struct edge{
int next,to;
}e[maxn];
inline void addedge(int next,int to)
{
e[++size].to=to;
e[size].next=head[next];
head[next]=size;
}
void dfs1(int t,int fat)
{
int i,j;
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
ls[j]=ls[t]+1;
dfs1(j,t);
if(dis[j]>dis[son[t]]) son[t]=j;
}
dis[t]=dis[son[t]]+1;
}
void dfs2(int t,int fat)
{
f[t][vnum[t]]=1;
if(son[t])
{
f[son[t]]=f[t]+27;
dfs2(son[t],t);
}
int i,j;
int k,l;
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
if(j==son[t]) continue;
f[j]=st;
st+=dis[j]*27;
dfs2(j,t);
for(k=1;k<=dis[j];k++)
for(l=1;l<=26;l++)
f[t][k*27+l]+=f[j][(k-1)*27+l];
}
for(i=0;i<q[t].size();i++)
{
int looker=0;
int tmph=q[t][i].first-ls[t];
int tbh=q[t][i].second;
if(tmph>=dis[t]||tmph<0)
{
ans[tbh]=1;
continue;
}
for(j=1;j<=26;j++)
{
if(f[t][tmph*27+j]&1) looker++;
}
if(looker==1||!looker) ans[tbh]=1;
}
}
int main()
{
register int i,j;
scanf("%d %d",&n,&m);
int t1,t2;
for(i=2;i<=n;i++)
{
scanf("%d",&t1);
addedge(t1,i);
}
char t;
scanf("\n");
for(i=1;i<=n;i++)
{
scanf("%c",&t);
vnum[i]=(t-'a'+1);
}
for(i=1;i<=m;i++)
{
scanf("%d %d",&t1,&t2);
q[t1].push_back(make_pair(t2,i));
}
ls[1]=1;
dfs1(1,1);
f[1]=st; st+=dis[1]*27;
dfs2(1,1);
for(i=1;i<=m;i++)
{
if(ans[i]) printf("Yes\n");
else printf("No\n");
}
return 0;
}
|
