树与异或问题题解

【前言】
此题比较简单。
【暴力】
枚举一条简单路径，枚举另一条简单路径，暴力判断是否有公共边。
复杂度O(n^4)或更高。
【正解】
根据异或的性质，x^y^y=x，所以说，两条简单路径的公共边在异或的过程中被抵消了，相当于没有选这些边，两条简单路径删除公共边的结果还会是两条简单路径，因此，有公共边这个条件可以无视。
所以问题变成了，找两条简单路径，求边最大异或和。
路径数最多n^2，但值域很小。
开个数组记录每个数是否出现即可。
复杂度O(1024*1024)

参考代码：

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @param aLen int a数组长度
     * @param b int整型一维数组 
     * @param bLen int b数组长度
     * @return int整型
     */
    int fa[10000],aa[10000],bz[10000],ans;
    int wwork(int n, int* a, int aLen, int* b, int bLen) {
        // write code here
        for (int i=1;i<n;i++) fa[i]=a[i-1];
    for (int i=1;i<n;i++) aa[i]=b[i-1],aa[i]^=aa[fa[i]];
    for (int i=1;i<=n;i++){
        bz[aa[i]]=1;
        for (int j=i+1;j<=n;j++)bz[aa[i]^aa[j]]=1;
    }
        ans=0;
    for (int i=0;i<=1024;i++)
        for (int j=i;j<=1024;j++)
            if (bz[i]&bz[j]) ans=max(i^j,ans);
    return ans;
    }
};