struct trie { int nex[100000][26], cnt; bool exist[100000]; // 该结点结尾的字符串是否存在 void insert(char *s, int l) { // 插入字符串 int p = 0; for (int i = 0; i < l; i++) { int c = s[i] - 'a'; if (!nex[p][c]) nex[p][c] = ++cnt; // 如果没有，就添加结点 p = nex[p][c]; } exist[p] = true; } bool find(char *s, int l) { // 查找字符串 int p = 0; for (int i = 0; i < l; i++) { int c = s[i] - 'a'; if (!nex[p][c]) return 0; p = nex[p][c]; } return exist[p]; }};
Python
class trie: def __init__(self): self.nex = [[0 for i in range(26)] for j in range(100000)] self.cnt = 0 self.exist = [False] * 100000 # 该结点结尾的字符串是否存在 def insert(self, s): # 插入字符串 p = 0 for i in s: c = ord(i) - ord("a") if not self.nex[p][c]: self.cnt += 1 self.nex[p][c] = self.cnt # 如果没有，就添加结点 p = self.nex[p][c] self.exist[p] = True def find(self, s): # 查找字符串 p = 0 for i in s: c = ord(i) - ord("a") if not self.nex[p][c]: return False p = self.nex[p][c] return self.exist[p]
Java
public class Trie { int[][] tree = new int[10000][26]; int cnt = 0; boolean[] end = new boolean[10000]; public void insert(String word) { int p = 0; char[] chars = word.toCharArray(); for (int i = 0; i < chars.length; i++) { int c = chars[i] - 'a'; if (tree[p][c] == 0) { tree[p][c] = ++cnt; } p = tree[p][c]; } end[p] = true; } public boolean find(String word) { int p = 0; char[] chars = word.toCharArray(); for (int i = 0; i < chars.length; i++) { int c = chars[i] - 'a'; if (tree[p][c] == 0) { return false; } p = tree[p][c]; } return end[p]; }}
#include <cstdio>using namespace std;constexpr int N = 500010;char s[N];int n, m, ch[N][26], tag[N], tot = 1;int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%s", s + 1); int u = 1; for (int j = 1; s[j]; ++j) { int c = s[j] - 'a'; // 如果这个节点的子节点中没有这个字符，添加上并将该字符的节点号记录为++tot if (!ch[u][c]) ch[u][c] = ++tot; u = ch[u][c]; // 往更深一层搜索 } tag[u] = 1; // 最后一个字符为节点 u 的名字未被访问到记录为 1 } scanf("%d", &m); while (m--) { scanf("%s", s + 1); int u = 1; for (int j = 1; s[j]; ++j) { int c = s[j] - 'a'; u = ch[u][c]; if (!u) break; // 不存在对应字符的出边说明名字不存在 } if (tag[u] == 1) { tag[u] = 2; // 最后一个字符为节点 u 的名字已经被访问 puts("OK"); } else if (tag[u] == 2) // 已经被访问，重复访问 puts("REPEAT"); else puts("WRONG"); } return 0;}
#include <algorithm>#include <iostream>using namespace std;constexpr int N = 100010;int head[N], nxt[N << 1], to[N << 1], weight[N << 1], cnt;int n, dis[N], ch[N << 5][2], tot = 1, ans;void insert(int x) { for (int i = 30, u = 1; i >= 0; --i) { int c = ((x >> i) & 1); // 二进制一位一位向下取 if (!ch[u][c]) ch[u][c] = ++tot; u = ch[u][c]; }}void get(int x) { int res = 0; for (int i = 30, u = 1; i >= 0; --i) { int c = ((x >> i) & 1); if (ch[u][c ^ 1]) { // 如果能向和当前位不同的子树走，就向那边走 u = ch[u][c ^ 1]; res |= (1 << i); } else u = ch[u][c]; } ans = max(ans, res); // 更新答案}void add(int u, int v, int w) { // 建边 nxt[++cnt] = head[u]; head[u] = cnt; to[cnt] = v; weight[cnt] = w;}void dfs(int u, int fa) { insert(dis[u]); get(dis[u]); for (int i = head[u]; i; i = nxt[i]) { // 遍历子节点 int v = to[i]; if (v == fa) continue; dis[v] = dis[u] ^ weight[i]; dfs(v, u); }}int main() { cin.tie(nullptr)->sync_with_stdio(false); cin >> n; for (int i = 1; i < n; ++i) { int u, v, w; cin >> u >> v >> w; add(u, v, w); // 双向边 add(v, u, w); } dfs(1, 0); cout << ans; return 0;}
给定一棵 n 个结点的有根树 T，结点从 1 开始编号，根结点为 1 号结点，每个结点有一个正整数权值 vi。
设 x 号结点的子树内（包含 x 自身）的所有结点编号为 c1,c2,…,ck，定义 x 的价值为：
val(x)=(vc1+d(c1,x))⊕(vc2+d(c2,x))⊕⋯⊕(vck+d(ck,x)) 其中 d(x,y)。
表示树上 x 号结点与 y 号结点间唯一简单路径所包含的边数，d(x,x)=0。⊕ 表示异或运算。
请你求出 i=1∑nval(i) 的结果。
