codechef Polo the Penguin and the Tree

一般xor 的题目都是用trie解决。

那这道题是在树上的trie;

首先：从root==1,遍历树得到1到所有节点的xor 值。

然后对于每个点我们把其插入二进制树中。

对于每一个点查找其二进值异或值最大的数依次遍历下来。

注意：边的数量开两倍以上，RE很多次。

find函数具体是这样的：

对于一个书二进值：10001000101

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<string>

 #include<cstring>

 #include<set>

 #include<map>

 #include<stdlib.h>

 #define N  223456

 using namespace std;

 struct edge

 {

   int v,w,next;

 }e[N];

 int tot,nid;

 int head[N],ans[N];

 int next[N*][];

 void add(int u,int v,int w)

 {

    e[tot].v=v;

    e[tot].w=w;

    e[tot].next=head[u];

    head[u]=tot++;

 }

 void dfs(int u,int fa)

 {

    for (int i=head[u];i!=-;i=e[i].next)

    {

       int v=e[i].v;

       if (v==fa) continue;

       ans[v]=ans[u]^e[i].w;

       dfs(v,u);

    }

 }

 void insert(int node,int d,int val)

 {

    if (d==)  return;

    int p=-d;

    int c=(val&(<<p))  ? :;

    if (next[node][c]==-) next[node][c]=++nid;

    insert(next[node][c],d+,val);

 }

 int solve(int node,int d,int val)

 {

   if (d==) return ;

   int p=-d;

   int c=(val&(<<p))?:;

   if (next[node][c]!=-)

   return (<<p)+solve(next[node][c],d+,val);

   return solve(next[node][!c],d+,val);

 }

 int main()

 {

   int T;

   scanf("%d",&T);

   while (T--)

   {

      int n;

      scanf("%d",&n);

      memset(head,-,sizeof(head));

      memset(next,-,sizeof(next));

      memset(ans,,sizeof(ans));

      tot=nid=;

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

      {

         int u,v,w;

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

         add(u,v,w);

         add(v,u,w);

      }

      dfs(,-);

      for (int i=;i<=n;i++) insert(,,ans[i]);

      int tmp=;

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

      tmp=max(tmp,solve(,,ans[i]));

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

      }

      return ;

   }

我们先要判断 01110111010

存在否，这样才能达到最大值

巴特西

codechef Polo the Penguin and the Tree

最新文章

热门文章