fork download
  1. from collections import defaultdict
  2.  
  3. def solve():
  4. N = int(input())
  5. tree = defaultdict(list)
  6. edge_string = {}
  7.  
  8. for _ in range(N-1):
  9. u, v, s = input().split()
  10. u = int(u)
  11. v = int(v)
  12. tree[u].append(v)
  13. edge_string[(u, v)] = s
  14.  
  15. slogan = input().strip()
  16. total = 0
  17.  
  18. # Perform DFS from root (0)
  19. stack = [(0, "")]
  20. while stack:
  21. node, current_str = stack.pop()
  22. full_str = current_str
  23.  
  24. # Check all children
  25. for child in tree[node]:
  26. new_str = full_str + edge_string[(node, child)]
  27. count = new_str.count(slogan)
  28. total += count
  29. stack.append((child, new_str))
  30.  
  31. print(total)
  32.  
  33. solve()
Success #stdin #stdout 0.1s 14120KB
stdin
11
0 2 Welcom
0 7 VietN
2 8 nauTK
7 3 am
7 9 nauTK
2 5 eKTuan
5 4 IOIKTuanIO
7 1 IOI
5 6 IOI23
4 10 I2023
KTuanIOI
stdout
4