字典树学习笔记

P2922 [USACO08DEC]Secret Message G
这是我第一次正式的去写的字典树的题。所以码风和相关细节上有点不太精简…
大致思路：直接建树之后，dfs把子树的值求出来，然后直接跑询问即可。比较简单，适合入门。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
#define fi first
#define se second
#define pb push_back
int n,m,x,f[N];
int cnt,ne[N][2],p[N][2];
int r,sz[N],vis[N];
void add(int res,int now){
  if(f[res]==0){
    if(p[now][0]==0){
      p[now][0]=++cnt;
    }
    if(res==x)sz[p[now][0]]++;
    else add(res+1,p[now][0]);
  }else{
    if(p[now][1]==0){
      p[now][1]=++cnt;
    }
    if(res==x)sz[p[now][1]]++;
    else add(res+1,p[now][1]);
  }
}
void dfs(int now){
  vis[now]=sz[now];
  if(p[now][1]){
    dfs(p[now][1]);
    vis[now]+=vis[p[now][1]];
  }
  if(p[now][0]){
    dfs(p[now][0]);
    vis[now]+=vis[p[now][0]];
  }
  //cout<<now<<' '<<vis[now]<<endl;
}
LL get(int res,int now){
  if(res>x){
    return vis[now]-sz[now];
  }
  LL ans=0;
  if(f[res]==1){
    if(p[now][1]){
      ans+=sz[p[now][1]];
      ans+=get(res+1,p[now][1]);
    }
  }else{
    if(p[now][0]){
      ans+=sz[p[now][0]];
      ans+=get(res+1,p[now][0]);
    }
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin>>n>>m;
  r=++cnt;
  for(int i=1;i<=n;i++){
    cin>>x;
    for(int j=1;j<=x;j++){
      cin>>f[j];
    }
    add(1,1);
  }
  dfs(1);
  for(int i=1;i<=m;i++){
    cin>>x;
    for(int j=1;j<=x;j++){
      cin>>f[j];
    }
    cout<<get(1,1)<<'\n';
  }
  return 0;
}

P4551 最长异或路径

第二题，主要的点就是 $d i s (i, j) = d i s (1, i) \oplus d i s (1, j)$ 。其中 $d i s (1, x)$ 表示1到x的路径边权异或和。
那么显然就是找两个异或起来最大的 $d i s$ 了。建完树枚举 $i$ ，贪心跑一下即可。
给出两份代码。一份很冗长的是我第一次写的，第二份是我借鉴大佬们后写的。。。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e6 + 10;
#define fi first
#define se second
#define pb push_back
vector<pair<int,int>>v[100005];
int n,m,f[N];
void dfs(int now,int pre){
  for(auto k:v[now]){
    if(k.fi==pre)
      continue;
    f[k.fi]=k.se^f[now];
    dfs(k.fi,now);
  }
}
int nx[N][2],cnt,r;
void add(int now,int pos,int x){
  if(now<0)return ;
  if((1<<now) & x){
    if(!nx[pos][1])nx[pos][1]=++cnt;
    add(now-1,nx[pos][1],x);
  }else{
    if(!nx[pos][0])nx[pos][0]=++cnt;
    add(now-1,nx[pos][0],x);
  }
}
int get(int x,int l,int r){
  if(x<0)return 0;
  int ans=0;
  if(nx[l][1] && nx[r][0]){
    ans=max((1<<x)^get(x-1,nx[l][1],nx[r][0]),ans);
  }
  if(nx[l][0] && nx[r][1]){
    ans=max(ans,(1<<x)^get(x-1,nx[l][0],nx[r][1]));
  }
  if(ans)return ans;
  if(nx[l][1]&&nx[r][1]){
    ans=max(ans,get(x-1,nx[l][1],nx[r][1]));
  }
  if(nx[l][0]&&nx[r][0]){
    ans=max(ans,get(x-1,nx[l][0],nx[r][0]));
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin>>n;
  for(int i=1;i<n;i++){
    int s,t,w;
    cin>>s>>t>>w;
    v[s].pb({t,w});
    v[t].pb({s,w});
  }
  dfs(1,0);
  r=++cnt;
  for(int i=1;i<=n;i++)add(30,r,f[i]);//cout<<i<<' '<<f[i]<<endl;
  cout<<get(30,1,1)<<'\n';
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e6 + 10;
#define fi first
#define se second
#define pb push_back
vector<pair<int,int>>v[100005];
int n,m,f[N];
void dfs(int now,int pre){
  for(auto k:v[now]){
    if(k.fi==pre)
      continue;
    f[k.fi]=k.se^f[now];
    dfs(k.fi,now);
  }
}
int nx[N][2],cnt,r;
void add(int now,int pos,int x){
  if(now<0)return ;
  if((1<<now) & x){
    if(!nx[pos][1])nx[pos][1]=++cnt;
    add(now-1,nx[pos][1],x);
  }else{
    if(!nx[pos][0])nx[pos][0]=++cnt;
    add(now-1,nx[pos][0],x);
  }
}
int get(int x,int now){
  int ans=0;
  for(int i=30;i>=0;i--){
    bool y=x&(1<<i);
    if(y&&!nx[now][!y]||!y&&nx[now][!y])ans|=1<<i;
    if(nx[now][!y])now=nx[now][!y];
    else now=nx[now][y];
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin>>n;
  for(int i=1;i<n;i++){
    int s,t,w;
    cin>>s>>t>>w;
    v[s].pb({t,w});
    v[t].pb({s,w});
  }
  dfs(1,0);
  r=++cnt;
  for(int i=1;i<=n;i++)add(30,r,f[i]);//cout<<i<<' '<<f[i]<<endl;
  int ans=0;
  for(int i=1;i<=n;i++){
    ans=max(ans,get(f[i],1)^f[i]);
  }
  cout<<ans<<'\n';
  return 0;
}

代码短看起来就是舒服啊…