Problem 1008. Hilarity

Brief description:

给定一颗边权树，求一条路径，最大化异或和。

Analysis:

Tire + 贪心 。）

（边表用 vector 会 TLE。）

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2815893

See also http://www.codechef.com/viewsolution/4993836

//}/* .................................................................................................................................. */

const int N = int(1e5) + 9, LV = 31;
int n;

void _r(int &x){
    x=reverse_bits(x); x>>=1;
}

namespace T{

    int trans[N*LV][2];
    int nn;

    int new_node(){
        RST(trans[nn]);
        return nn++;
    }

    #define v trans[u][c]

    void Insert(int x){
        _r(x); int u = 0; REP(i, LV){
            int c = x & 1; x >>= 1;
            if (!v) v = new_node();
            u = v;
        }
    }
    int Query(int x){
        int z = 0, u = 0; _r(x); REP(i, LV){
            int c = (x & 1) ^ 1; x >>= 1; z <<= 1;
            if (!v) c ^= 1; else z |= 1;
            u = v;
        }
        return z;
    }
    void Init(){
        nn = 0; new_node();
    }
};

#define aa to[i^1]
#define bb to[i]
#define v bb
#define w ww[i/2]

const int M = N*2;
int hd[N], suc[M], to[M], ww[N];
int Xor[N], maxXor;

void dfs(int u = 0, int p = -1){

    T::Insert(Xor[u]);
    checkMax(maxXor, T::Query(Xor[u]));

    REP_G(i, u) if (v != p){
        Xor[v] = Xor[u] ^ w;
        dfs(v, u);
    }
}


int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    while (~scanf("%d", &n)){

        fill(hd, hd+n, 0); FOR_C(i, 2, n<<1){
            RD(aa, bb, w);
            suc[i] = hd[aa], hd[aa] = i++;
            suc[i] = hd[aa], hd[aa] = i;
        }

        maxXor = 0; T::Init(); dfs();
        OT(maxXor);
    }
}

Posted by xiaodao
Category: 日常