# ACM学习历程—POJ 3764 The xor-longest Path（xor && 字典树 && 贪心）

```#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>
#define LL long long

using namespace std;

const int maxN = 100005;

//求n个数中取出两个数能xor的最大值
//Trie Tree字典树
//len*n, len为数的二进制最大长度
const int len = 31;//len表示数的二进制最大长度
struct Trie
{
int next[2];
}tree[maxN*len];
int cntTree;

void initTree()
{
cntTree = 0;
memset(tree, -1, sizeof(tree));
}

{
int now = 0;
bool k;
for (int i = len; i >= 0; i--)
{
k = x&(1<<i);
if (tree[now].next[k] == -1)
tree[now].next[k] = ++cntTree;
now = tree[now].next[k];
}
}

//返回当前数中能和x合成最大数的数
int query(int x)
{
int v = 0, now = 0;
bool k;
for (int i = len; i >= 0; i--)
{
k = x&(1<<i);
if (tree[now].next[!k] != -1)
k = !k;
v = v|(k<<i);
now = tree[now].next[k];
}
return v;
}

//链式前向星
struct Edge
{
int to, next;
int val;
}edge[maxN*2];

void addEdge(int u, int v, int w)
{
edge[cnt].to = v;
edge[cnt].val = w;
cnt++;
}

void initEdge()
{
cnt = 0;
}

int n, p[maxN];

void dfs(int now)
{
int to;
for (int i = head[now]; i != -1; i = edge[i].next)
{
to = edge[i].to;
if (p[to] == -1)
{
p[to] = p[now]^edge[i].val;
dfs(to);
}
}
}

void input()
{
initEdge();
memset(p, -1, sizeof(p));
int u, v, w;
for (int i = 1; i < n; ++i)
{
scanf("%d%d%d", &u, &v, &w);
}
p[0] = 0;
dfs(0);
}

void work()
{
int ans = 0;
initTree();
for (int i = 0; i < n; ++i)
{
ans = max(ans, p[i]^query(p[i]));
}
printf("%d\n", ans);
}

int main()
{
//freopen("test.in", "r", stdin);
while (scanf("%d", &n) != EOF)
{
input();
work();
}
return 0;
}```

## ACM学习历程——POJ3468 A Simple Problem with Integers（线段树）

Description You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval. In

## ACM学习历程—HDU 4726 Kia&#39;s Calculation（ 贪心&amp;&amp;计数排序）

DescriptionDoctor Ghee is teaching Kia how to calculate the sum of two integers. But Kia is so careless and alway forget to carry a number when the sum of two digits exceeds 9. For example, when she calculates 4567+5789, she will get 9246, and for 12

## ACM学习历程—HDU 5023 A Corrupt Mayor&#39;s Performance Art（广州赛区网赛）（线段树）

Problem Description Corrupt governors always find ways to get dirty money. Paint something, then sell the worthless painting at a high price to someone who wants to bribe him/her on an auction, this seemed a safe way for mayor X to make money. Becaus

## 2014百度之星资格赛—— Xor Sum（01字典树）

Xor Sum Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others) Total Submission(s): 0    Accepted Submission(s): 0 Problem Description Zeus 和 Prometheus 做了一个游戏,Prometheus 给 Zeus 一个集合,集合中包含了N个正整数,随后 Prometheus 将向 Zeus 发起

## HDU 4825 Xor Sum（经典01字典树+贪心）

Xor Sum Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others) Total Submission(s): 1555    Accepted Submission(s): 657 Problem Description Zeus 和 Prometheus 做了一个游戏,Prometheus 给 Zeus 一个集合,集合中包含了N个正整数,随后 Prometheus 将向 Ze