fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int ALPHABET_SIZE = 26;
  5. int to_index(char c) { return c-'a'; }
  6.  
  7. struct trie_node {
  8.     bool word_end;
  9.     int size;
  10.     trie_node *son[ALPHABET_SIZE];
  11.     trie_node() { word_end=false; size=0; memset(son,0,sizeof(son)); }
  12. };
  13.  
  14. trie_node* grow_upwards(trie_node* root, char c) {
  15.     if (!root) root = new trie_node();
  16.     trie_node *new_root = new trie_node();
  17.     new_root->son[ to_index(c) ] = root;
  18.     root->word_end = true;
  19.     ++(root->size);
  20.     new_root->size = root->size;
  21.     return new_root;
  22. }
  23.  
  24. trie_node* merge(trie_node* left, trie_node* right) {
  25.     if (!left) return right;
  26.     if (!right) return left;
  27.     left->size = 0;
  28.     for (int c=0; c<ALPHABET_SIZE; ++c) {
  29.         left->son[c] = merge( left->son[c], right->son[c] );
  30.         if (left->son[c]) left->size += left->son[c]->size;
  31.     }
  32.     left->word_end |= right->word_end;
  33.     if (left->word_end) ++(left->size);
  34.     return left;
  35. }
  36.  
  37. vector< vector<int> > T;
  38. string S;
  39. vector<int> C;
  40. vector<bool> visited;
  41.  
  42. trie_node* dfs(int kde) {
  43.     visited[kde] = true;
  44.     vector<trie_node*> deti;
  45.     for (int kam : T[kde]) if (!visited[kam]) deti.push_back( dfs(kam) );
  46.     trie_node *root = grow_upwards( NULL, S[kde] );
  47.     for (auto &x : deti) {
  48.         x = grow_upwards( x, S[kde] );
  49.         root = merge( root, x );
  50.     }
  51.     C[kde] += root->size;
  52.     return root;
  53. }
  54.  
  55. int main() {
  56.     int N;
  57.     cin >> N;
  58.     C.resize(N);
  59.     for (int &c:C) cin >> c;
  60.     cin >> S;
  61.     T.resize(N);
  62.     for (int n=0; n<N-1; ++n) {
  63.         int a, b; cin >> a >> b; --a; --b;
  64.         T[a].push_back(b);
  65.         T[b].push_back(a);
  66.     }
  67.     visited.resize(N,false);
  68.     dfs(0);
  69.     int maxval = *max_element( C.begin(), C.end() );
  70.     int maxcnt = 0;
  71.     for (int &c:C) if (c==maxval) ++maxcnt;
  72.     cout << maxval << endl << maxcnt << endl;
  73. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
10
1 2 7 20 20 30 40 50 50 50
cacabbcddd
1 2
6 8
7 2
6 2
5 4
5 9
3 10
2 5
2 3
stdout
copy 
51
3
https://ideone.com/VTJ7dH
language:
C++14 (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!