BZOJ 3926

传送门

陈老师语文水平高超+1 2333

太阳花田的结构比较特殊,只与一个空地相邻的空地数量不超过20个。(因为很重要所以再发一遍)

找到这20个叶子节点,然后DFS20遍,把遇到的节点扔到自动机里就行了


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
program bzoj_3926;
const maxn=100000;
var n,c,i,tot,a,b,np,q,nq:longint;
mx,fa:array[1..2*maxn*20+1]of longint;
son:array[1..2*maxn*20+1,0..9]of longint;
l:array[1..maxn*2]of record ed,pre:longint; end;
lst,col,cnt:array[1..maxn]of longint;
ans:int64;
procedure link(a,b:longint);
begin
inc(tot);
l[tot].pre:=lst[a];
lst[a]:=tot;
l[tot].ed:=b;
end;
function extend(p,c:longint):longint;
var i:longint;
begin
inc(tot);
np:=tot;
mx[np]:=mx[p]+1;
while (p<>0)and(son[p,c]=0) do
begin
son[p,c]:=np;
p:=fa[p];
end;
if p=0 then fa[np]:=1 else
begin
q:=son[p,c];
if mx[p]+1=mx[q] then fa[np]:=q else
begin
inc(tot);
nq:=tot;
for i:=0 to 9 do son[nq,i]:=son[q,i];
fa[nq]:=fa[q];
fa[q]:=nq;
fa[np]:=nq;
mx[nq]:=mx[p]+1;
while (p<>0)and(son[p,c]=q) do
begin
son[p,c]:=nq;
p:=fa[p];
end;
end;
end;
exit(np);
end;
procedure dfs(i,fa,p:longint);
var k,np:longint;
begin
np:=extend(p,col[i]);
k:=lst[i];
while k<>0 do
begin
if l[k].ed<>fa then dfs(l[k].ed,i,np);
k:=l[k].pre;
end;
end;
begin
readln(n,c);
for i:=1 to n do read(col[i]);
tot:=0;
for i:=1 to n do cnt[i]:=0;
for i:=1 to n-1 do
begin
readln(a,b);
link(a,b);
link(b,a);
inc(cnt[a]);
inc(cnt[b]);
end;
tot:=1;
for i:=1 to n do if cnt[i]=1 then dfs(i,0,1);
ans:=0;
for i:=1 to tot do inc(ans,mx[i]-mx[fa[i]]);
writeln(ans);
end.