BZOJ

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.