這題意思很簡單。求一棵樹里面的一條路徑，使得其異或權(quán)(就是將路徑里面所有邊的權(quán)值異
或起來)最大。
這個題有兩步。第一步是假定根為節(jié)點0，求出根到其它節(jié)點的異或距離，保存在數(shù)組xor里面，
這個dfs一下即可。然后，用xor[i]^xor[j]就能代表節(jié)點i到節(jié)點j的路徑。這個結(jié)論可以這么看。
如果，i和j之間的路徑經(jīng)過根節(jié)點，那么上面的結(jié)論肯定是正確的。如果，該路徑不經(jīng)過根，那么
xor[i]和xor[j]必定保護從根到某個節(jié)點的相同的一段子路徑，根據(jù)異或的性質(zhì)，這段子路徑會
被消掉，所以這個結(jié)論也是這確的。。。
第二步就是枚舉，xor[i]^xor[j]使得結(jié)果最大了。如果直接暴力，平方的算法肯定會超時的。
由于每個值可以表示成2進制，如果把其它xor值都保存在字典樹里面，用當前的xor[i]去字典樹
里面，一遍就可以找到異或最大值。
另外，由于樹的點數(shù)太多，只能用鄰接表，用vector模擬鄰接表果斷超時了。。。
改成靜態(tài)鏈表才過。。。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 100010;
int nXor[MAX];
bool bVis[MAX];
int nFirst[MAX];
struct Edge
{
int nE;
int nW;
int nNext;
};
Edge egs[MAX * 2];
struct Node
{
Node* pSons[2];
};
Node nodes[MAX * 32];
Node* pRoot = &nodes[0];
int nNew;
void GetBCode(
int nL,
int* nBCode,
int& nLen)
{
nLen = 0;
while (nLen <= 30)
{
nBCode[nLen++] = nL % 2;
nL >>= 1;
}
reverse(nBCode, nBCode + nLen);
}
void Insert(
int nL)
{
int nLen = 0;
int i = 0;
int nBCode[32];
GetBCode(nL, nBCode, nLen);
Node* pNode = pRoot;
while (i < nLen)
{
if (pNode->pSons[nBCode[i]])
{
pNode = pNode->pSons[nBCode[i]];
}
else {
memset(nodes + nNew, 0,
sizeof(nodes[nNew]));
pNode->pSons[nBCode[i]] = nodes + nNew;
pNode = nodes + nNew;
++nNew;
}
++i;
}
}
int FindMax(
int nL)
{
int nLen = 0;
int nAns = 0;
int i = 0;
int nBCode[32];
Node* pNode = pRoot;
GetBCode(nL, nBCode, nLen);
while (i < nLen)
{
int nBest = (nBCode[i] == 0 ? 1 : 0);
int nBad = (nBCode[i] == 0 ? 0 : 1);
if (pNode->pSons[nBest])
{
nAns = 2 * nAns + nBest;
pNode = pNode->pSons[nBest];
}
else if (pNode->pSons[nBad])
{
nAns = 2 * nAns + nBad;
pNode = pNode->pSons[nBad];
}
else break;
++i;
}
return nAns ^ nL;
}
void Dfs(
int nV,
int nL)
{
nXor[nV] = nL;
bVis[nV] =
true;
for (
int e = nFirst[nV]; e != -1; e = egs[e].nNext)
{
if (!bVis[egs[e].nE])
{
Dfs(egs[e].nE, nL ^ egs[e].nW);
}
}
}
int main()
{
int nN;
int nU, nV, nW;
while (scanf("%d", &nN) == 1)
{
for (
int i = 0; i < nN; ++i) nFirst[i] = -1;
for (
int i = 1, j = 0; i < nN; ++i)
{
scanf("%d%d%d", &nU, &nV, &nW);
egs[j].nE = nV;
egs[j].nW = nW;
egs[j].nNext = nFirst[nU];
nFirst[nU] = j++;
egs[j].nE = nU;
egs[j].nW = nW;
egs[j].nNext = nFirst[nV];
nFirst[nV] = j++;
}
memset(bVis,
false,
sizeof(
bool) * nN);
Dfs(0, 0);
memset(&nodes[0], 0,
sizeof(Node));
nNew = 1;
int nAns = 0;
for (
int i = 0; i < nN; ++i)
{
nAns = max(nAns, FindMax(nXor[i]));
Insert(nXor[i]);
}
printf("%d\n", nAns);
}
return 0;
}