小圆前辈的异或树

C++(clang++11) 解法, 执行用时: 315ms, 内存消耗: 16052K, 提交时间: 2021-04-29 09:43:44

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e5+10,M=2*N;
int rt,mx,sz[N];
int h[N],e[M],ne[M],idx;
int vis[N];
int n;
int val[N];//权值
int ans=0;
int d[N];//记录抑或值
int q[N],r=0;//记录
int son[N*23][2],tot;
inline void Insert(int x)
{
    int p=0;
    for(int i=22;i>=0;i--)
    {
        int k=x>>i&1;
        if(!son[p][k])son[p][k]=++tot;
        p=son[p][k];
    }
}
inline int find(int x)
{
    int p=0;
    int res=0;
    for(int i=22;i>=0;i--)
    {
        int k=x>>i&1^1;
        if(son[p][k])
        {
            res+=1<<i;
            p=son[p][k];
        }else p=son[p][k^1];
    }
    return res;
}
inline void get_rt(int u,int fa,int tot)
{
    sz[u]=1;
    int son=0;
    for(int i=h[u];i;i=ne[i])
    {
        int v=e[i];
        if(vis[v]||v==fa)continue;
        get_rt(v,u,tot);
        sz[u]+=sz[v];
        son=max(son,sz[v]);
    }
    son=max(son,tot-sz[u]);
    if(son<mx)mx=son,rt=u;
}
inline void add(int u,int v)
{
    e[++idx]=v;ne[idx]=h[u];h[u]=idx;
}
inline void get_dis(int u,int fa,int cur)
{
    q[++r]=cur;
    ans=max(ans,cur);
    for(int i=h[u];i;i=ne[i])
    {
        int j=e[i];
        if(j==fa||vis[j])continue;
        get_dis(j,u,cur^val[j]);
    }
}
inline void init()
{
    for(int i=0;i<=tot;i++)
        for(int j=0;j<2;j++)son[i][j]=0;
    tot=0;
}
inline void calc(int u)
{
    d[u]=0;r=0;
    get_dis(u,0,0);
    init();
    for(int i=1;i<=r;i++)Insert(q[i]);
    for(int i=1;i<=r;i++)
    ans=max(find(q[i]^val[u]),ans);
    
}
inline void dfs(int u)//分治
{
    calc(u);
    vis[u]=1;
    for(int i=h[u];i;i=ne[i])
    {
        int v=e[i];
        if(vis[v])continue;
        mx=inf;
        get_rt(v,0,sz[v]);
        dfs(rt);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&val[i]);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);add(b,a);
    }
    mx=inf;
    get_rt(1,0,n);
    dfs(rt);
    printf("%d",ans);
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 262ms, 内存消耗: 28880K, 提交时间: 2023-07-11 14:46:24

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int N = 200010;

int tr[N * 23][2], idx, sz[N];
vector<int> adj[N];
int a[N], s[N], res;
int l[N], r[N], seq[N], son[N], ts;
int n;

void dfs_pre(int u, int fa) {
  s[u] = a[u] ^ s[fa];
  l[u] = ++ts;
  seq[ts] = u;
  sz[u] = 1;
  for (auto v : adj[u]) {
    if (v == fa) continue;
    dfs_pre(v, u);  
    sz[u] += sz[v];
    if (sz[v] > sz[son[u]]) son[u] = v;
  }
  r[u] = ts;
}

void insert(int x) {
  int p = 0;
  for (int i = 22; ~i; i--) {
    int u = x >> i & 1;
    if (!tr[p][u]) tr[p][u] = ++idx;
    p = tr[p][u];
  }
}

int query(int x) {
  int res = 0, p = 0;
  for (int i = 22; ~i; i--) {
    int u = x >> i & 1;
    if (tr[p][!u]) {
      res |= 1 << i;
      p = tr[p][!u];
    } else {
      p = tr[p][u];
    }
  }
  return res;
}

void dfs(int u, int fa, bool clear) {
  for (auto v : adj[u]) {
    if (v == son[u] || v == fa) continue;
    dfs(v, u, true);
  }
  if (son[u]) dfs(son[u], u, false);
  for (auto v : adj[u]) {
    if (v == son[u] || v == fa) continue;
    for (int p = l[v]; p <= r[v]; p++) res = max(res, query(s[seq[p]] ^ a[u]));
    for (int p = l[v]; p <= r[v]; p++) insert(s[seq[p]]);
  }
  res = max(res, query(s[u] ^ a[u]));
  insert(s[u]);
  if (clear) {
    for (int i = 0; i <= idx; i++) {
      tr[i][0] = tr[i][1] = 0;
    }  
    idx = 0;
  }
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    res = max(res, a[i]);
  }
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }
  dfs_pre(1, 0);
  dfs(1, 0, false);
  cout << res << '\n';
  return 0;
}

详情