【poj3764】 The xor-longest Path

时间：2022-04-13 09:45:46

http://poj.org/problem?id=3764 (题目链接)

今天的考试题，看到异或就有点虚，根本没往正解上想。。

题意

　　给出一棵带权树，请找出树上的一条路径，使其边上权值的异或和最大。

solution

　　首先我们考虑从根向下dfs，记录下每个点i到根上权值的异或和${val[i]}$。根据异或和的性质：${x~Xor~y~Xor~y=x}$。所以我们可以由${val}$数组两两组合得出树上任意两点之间路径的异或和。（不理解请自己脑补OvO）

　　然而这样对于时间复杂度并没有提高，仍然需要枚举两点。所以我们考虑从异或这个运算的本质下手。要使两个数的异或和尽可能大，那么这两个数的二进制高位的数就要尽可能不同。其实这是贪心思想，对于每一个${val[i]}$，我们把它拆成二进制数，由高位向低位，尽可能使当前位上的数与${val[i]}$当前位上的数不同（这样对答案的贡献最大）。

　　对于这样一个算法，我们可以用trie树维护。根据深度建树30层，每一个节点的儿子就是${0}$和${1}$，表示有没有一个${val[i]}$在这一位存在${0}$或${1}$。这样就很好的解决了问题。复杂度${O（n*30）}$。

代码

// poj3764

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#define MOD 1000000007

#define inf 2147483640

#define LL long long

#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);

using namespace std;

const int maxn=100010;

struct edge {int to,next,w;}e[maxn<<1];

int vis[maxn],val[maxn],bin[maxn],tr[maxn<<4][2],head[maxn],cnt,sz,n;

void link(int u,int v,int w) {

	e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].w=w;

	e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;e[cnt].w=w;

}

void dfs(int u,int w) {

    vis[u]=1;

    for (int i=head[u];i;i=e[i].next) if (!vis[e[i].to])

            dfs(e[i].to,w^e[i].w);

    val[u]=w;

}

void insert(int x) {

    int u=0;

    for (int i=30;i>=0;i--) {

        int k=x&bin[i];k>>=i;

        if (!tr[u][k]) tr[u][k]=++sz;

        u=tr[u][k];

    }

}

int main() {

    bin[0]=1;for (int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;

    while (scanf("%d",&n)!=EOF) {

        cnt=sz=0;

        memset(vis,0,sizeof(vis));memset(head,0,sizeof(head));

        memset(tr,0,sizeof(tr));

        for (int u,v,w,i=1;i<n;i++) {

            scanf("%d%d%d",&u,&v,&w);

			u++,v++; //因为节点编号是从0开始，所以全部+1

			link(u,v,w);

        }

        dfs(1,0);

        for (int i=1;i<=n;i++) insert(val[i]);

        int ans=0;

        for (int i=0;i<=n;i++) {

            int u=0,x=val[i],s=0;

            for (int j=30;j>=0;j--) {

                int k=x&bin[j];k>>=j;

                if (tr[u][k^1]) s+=bin[j],u=tr[u][k^1];

                else u=tr[u][k];

            }

            ans=max(ans,s);

        }

        printf("%d\n",ans);

    }

    return 0;

}

　　

　　

相关文章