voidinsert(const std::string& s){ auto c = root; for (constauto& i : s) { c = ((c->son.find(i) != c->son.end()) ? c->son[i] : (c->son[i] = std::make_shared<Node>())); } c->v = true; }
boolquery(const std::string& s){ auto c = root; for (constauto& i : s) { if (c->son.find(i) != c->son.end()) { // do something here c = c->son[i]; } else { returnfalse; } } return c->v; } };
voidinsert(const std::string& s){ int c = 1; for (constauto& i : s) { constauto x = i - 'a'; // 这里还是要视字符集而定 c = (trie[c].son[x] ? trie[c].son[x] : (trie[c].son[x] = ++cnt)); } trie[c].v = true; }
boolquery(const std::string& s){ int c = 1; for (constauto& i : s) { constauto x = i - 'a'; // 同上 if (trie[c].son[x]) { // 同 c = trie[c].son[x]; } else { returnfalse; } } return trie[c].v; }
auto c = root; for (constauto& i : s) { constauto x = i - 'a'; if (c->v) { returnfalse; } for (int j = 0; j < 26; j++) { if (x != j and c->son.find(j + 'a') != c->son.end() and !e[x][j]) { e[x][j] = true; d[j]++; } } c = c->son[i]; } topos(std::move(e), d);
for (int i = 0; i < 26; i++) { if (d[i]) { returnfalse; } } returntrue; }
structNode { bool m; bool v; int son[32]; } trie[MAX_N];
int cnt = 1, ans, n; std::string as;
voidinsert(const std::string& s);
voidsolve(int k);
intmain(){ std::ios::sync_with_stdio(false);
int m{}, p{}; std::cin >> n; for (int i = 1; i <= n; i++) { std::cin >> s[i]; if (m < s[i].length()) { m = s[i].length(); p = i; } insert(s[i]); }
{ int c = 1; for (constauto& i : s[p]) { constauto x = i - 'a'; c = trie[c].son[x]; trie[c].m = true; } }
solve(1);
return0; }
voidinsert(const std::string& s){ int c = 1; for (constauto& i : s) { constauto x = i - 'a'; c = (trie[c].son[x] ? trie[c].son[x] : (trie[c].son[x] = ++cnt)); } trie[c].v = true; }
voidsolve(int k){ if (trie[k].v) { ans++; as.push_back('P'); } if (ans == n) { std::cout << as.length() << '\n'; for (constauto& i : as) { std::cout << i << '\n'; } return; }
for (int x = 0; x < 26; x++) { if (trie[k].son[x] and !trie[trie[k].son[x]].m) { as.push_back(x + 'a'); solve(trie[k].son[x]); as.push_back('-'); } }
for (int x = 0; x < 26; x++) { if (trie[k].son[x] and trie[trie[k].son[x]].m) { as.push_back(x + 'a'); solve(trie[k].son[x]); as.push_back('-'); } } }
int n; read(n); for (int i = 1; i < n; i++) { int u, v, w; read(u, v, w); create(u, v, w); create(v, u, w); } dfs(1, 0);
auto trie = std::make_unique<Trie>(); for (int i = 1; i <= n; i++) { trie->insert(a[i]); }
int ans = 0; for (int i = 1; i <= n; i++) { ans = std::max(ans, trie->query(a[i])); } std::cout << ans << '\n';
return0; }
voidcreate(int u, int v, int w){ node[++cnt].v = v; node[cnt].nxt = head[u]; node[cnt].w = w; head[u] = cnt; }
voiddfs(int x, int f){ for (int i = head[x]; i; i = node[i].nxt) { int v = node[i].v, w = node[i].w; if (v == f) { continue; } a[v] = a[x] ^ w; dfs(v, x); } }
voidTrie::insert(int a){ auto c = root; for (int i = MAX_L; i >= 0; i--) { constint x = (a >> i) & 1; c = (c->son[x] ? c->son[x] : (c->son[x] = std::make_shared<Node>())); } }
intTrie::query(int a){ auto c = root; int ans{0}; for (int i = MAX_L; i >= 0; i--) { constint x = (a >> i) & 1; if (c->son[x ^ 1]) { c = c->son[x ^ 1]; ans = (ans << 1) | (x ^ 1); } else { c = c->son[x]; ans = (ans << 1) | x; } } return ans ^ a; }
template <typename T> T read(){ T x = 0, f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); } return x * f; }
template <typename T> voidread(T& t){ t = read<T>(); }
voidTrie::pushdown(constint& x){ if (!lc) { lc = ++cnt; } if (!rc) { rc = ++cnt; } if (trie[x].t) { if (!trie[lc].v) { trie[lc].t += trie[x].t; trie[lc].a += trie[x].t; } if (!trie[rc].v) { trie[rc].t += trie[x].t; trie[rc].a += trie[x].t; } trie[x].t = 0; } }
voidTrie::mod(const std::string& s, constint& mv){ int c = 1; for (constauto& i : s) { constauto x = i - '0'; pushdown(c); c = trie[c].son[x]; } trie[c].v += mv; trie[c].a += 1; trie[c].t += 1; }
intTrie::query(const std::string& s){ int c = 1; for (constauto& i : s) { constauto x = i - '0'; pushdown(c); c = trie[c].son[x]; } return trie[c].a; }
intTrie::query(constint& r, constint& mx, constint& my){ int x = r; for (int d = 0; d < mx; d++) { pushdown(x); x = trie[x].son[(int)((bool)(my & (1 << d)))]; } return trie[x].a; }
#undef lc #undef rc
template <typename T> T read(){ T x = 0, f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); } return x * f; }
template <typename T> voidread(T& t){ t = read<T>(); }