fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8.  
  9. const int MAXC = 10, MAXN = (int) 1e5, MAXV = MAXN * 20;
  10.  
  11. struct edge {
  12. 	int to;
  13. 	edge *next;
  14. };
  15.  
  16. edge *son[MAXN + 10], e[MAXN * 2 + 10], *edge_cnt = e;
  17.  
  18. inline void add_edge(int x, int y) {
  19. 	edge_cnt++;
  20. 	edge_cnt->to = y;
  21. 	edge_cnt->next = son[x];
  22. 	son[x] = edge_cnt;
  23. }
  24.  
  25. struct node {
  26. 	int value;
  27. 	node *parent, *trans[MAXC];
  28. };
  29.  
  30. node pool[MAXV * 2 + 10], *node_cnt = pool;
  31.  
  32. inline node* new_node(int _value) {
  33. 	node *x = node_cnt++;
  34. 	x->value = _value;
  35. 	return x;
  36. }
  37.  
  38. node *root = new_node(0);
  39.  
  40. node* extend(node *p, int x) {
  41. 	node *np = new_node(p->value + 1);
  42. 	while (p && p->trans[x] == NULL)
  43. 		p->trans[x] = np, p = p->parent;
  44. 	if (p == NULL)
  45. 		np->parent = root;
  46. 	else {
  47. 		node *q = p->trans[x];
  48. 		if (p->value + 1 == q->value)
  49. 			np->parent = q;
  50. 		else {
  51. 			node *nq = new_node(p->value + 1);
  52. 			memcpy(nq->trans, q->trans, sizeof q->trans);
  53. 			nq->parent = q->parent;
  54. 			q->parent = nq;
  55. 			np->parent = nq;
  56. 			while (p && p->trans[x] == q)
  57. 				p->trans[x] = nq, p = p->parent;
  58. 		}
  59. 	}
  60. 	return np;
  61. }
  62.  
  63. int n, c, a[MAXN + 10], degree[MAXN + 10];
  64.  
  65. void dfs(int x, int pre, node *last) {
  66. 	node *temp = extend(last, a[x]);
  67. 	for (edge *i = son[x]; i; i = i->next)
  68. 		if (i->to != pre)
  69. 			dfs(i->to, x, temp);
  70. }
  71.  
  72. int main() {
  73. 	scanf("%d%d", &n, &c);
  74. 	for (int i = 1; i <= n; ++i)
  75. 		scanf("%d", &a[i]);
  76. 	for (int i = 2; i <= n; ++i) {
  77. 		int x, y;
  78. 		scanf("%d%d", &x, &y);
  79. 		add_edge(x, y);
  80. 		add_edge(y, x);
  81. 		degree[x]++;
  82. 		degree[y]++;
  83. 	}
  84. 	for (int i = 1; i <= n; ++i)
  85. 		if (degree[i] == 1)
  86. 			dfs(i, 0, root);
  87. 	ll ans = 0;
  88. 	for (node* i = pool; i != node_cnt; ++i)
  89. 		if (i->parent)
  90. 			ans += i->value - i->parent->value;
  91. 	cout << ans << '\n';
  92. 	return 0;
  93. }
Success #stdin #stdout 0s 193408KB
comments (?)
stdin
copy 
7 3
0 2 1 2 1 0 0
1 2
3 4
3 5
4 6
5 7
2 5
stdout
copy 
30
https://ideone.com/Aqyruc
substring, suffix automaton
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!