M_sea

洛谷4551 最长异或路径
LuoguPOJ分析POJ数据除了从0开始应该没什么不同了吧qwq 为什么我WA了qwq异或满足可减性,可以维护树...
扫描右侧二维码阅读全文
06
2018/12

洛谷4551 最长异或路径

Luogu

POJ

分析

POJ数据除了从0开始应该没什么不同了吧qwq 为什么我WA了qwq

异或满足可减性,可以维护树上前缀和(这里是异或和)。

记$u$到$1$的路径的异或和为$d[u]$,显然$u$到$v$的路径的异或和为$d[u]\ \operatorname{xor}\ d[v]$。

因为它们的$LCA$到$1$的那一段抵消掉了。

然后就变成了,找到两个点$u$和$v$,使得$d[u]\ \operatorname{xor}\ d[v]$最大。

可以建一颗0-1 Trie,然后从高位到低位贪心地选,尽量选与这一位不同的。

最后求一个最大值即可。插入一个数和查询一个数都是$O(31)$的,总时间复杂度大概是$O(31n)$,可以看成$O(n)$带了一个很大的常数qwq

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100000+10;

struct Edge { int v,w,nxt; };
Edge e[MAXN<<1];
int head[MAXN],cnt=0;

inline void addEdge(int u,int v,int w) {
    e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=head[u],head[u]=cnt;
}

int d[MAXN];

inline void Dfs(int u,int fa) {
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;
        if (v==fa) continue;
        d[v]=d[u]^w; Dfs(v,u);
    }
}

struct Trie { //0-1 Trie
    int son[MAXN*31][2];
    int cnt;
    Trie() { this->cnt=0; }
    inline void insert(int x) {
        for (re int i=1<<30,u=0;i;i>>=1) {
            int k=(x&i)?1:0;
            if (!son[u][k]) son[u][k]=++cnt;
            u=son[u][k];
        }
    }
    inline int query(int x) {
        int ans=0;
        for (re int i=1<<30,u=0;i;i>>=1) {
            int k=(x&i)?1:0;
            if (son[u][k^1]) ans+=i,u=son[u][k^1];
            else u=son[u][k];
        }
        return ans;
    }
} T;

int main() {
    int n=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read(),w=read();
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
    Dfs(1,0);
    for (re int i=1;i<=n;++i) T.insert(d[i]);
    int ans=0;
    for (re int i=1;i<=n;++i) ans=max(ans,T.query(d[i]));
    printf("%d\n",ans);
    return 0;
}
最后修改:2018 年 12 月 07 日 10 : 20 PM

发表评论

4 条评论

  1. smy

    不就是nlogn吗qwq

    1. M_sea
      @smy

      似乎很有道理。。

      但是实际上比$O(n\log n)$大吧qwq

      1. smy
        @M_sea

        也不能说O(n)*大常数吧qwq

        或者说是O(nlog值域)

        1. M_sea
          @smy

          有道理qwq但是懒得改了qwq