题解：P13308 故障

ymx2009 · 2025-10-29 22:52:48 · 题解

这是一个唐氏 01Tire 的做法。

思路分析

当一个节点要与父亲节点断开时，那么这棵树包含根的联通块大小将减少这个以这个节点为根子树的节点个数，并且以这个节点为根新开一棵树。
虽然可以一直除二来找到这个棵子树的根，但我想用 01Tire 来找根。
二叉树层次遍历编号满足每个节点的祖先节点的二进制是他的二进制的前缀。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+5;
int n,m,ans,tire[N][2],idx,f[N],dep[N];
bool exist[N];
unordered_map<int,bool> p;

int insert(int x)
{
    int root=0;
    vector<bool> t;
    for(;x;x>>=1) t.push_back(x&1);
    reverse(t.begin(),t.end());
    for(auto u:t)
    {
        if(!tire[root][u]) tire[root][u]=++idx,dep[tire[root][u]]=dep[root]+1;
        root=tire[root][u];
    }
    exist[root]=true;
    return root;
}

int query(int x)
{
    int root=0,res=0;
    vector<bool> t;
    for(;x;x>>=1) t.push_back(x&1);
    reverse(t.begin(),t.end());
    for(auto u:t)
    {
        // cout<<tmp<<' '<<root<<endl;
        if(!tire[root][u]) break;
        root=tire[root][u];
        if(exist[root]) res=root;
    }
    return res;
}

int query2(int root,int top)
{
    if(exist[root]&&root!=top) return (1ll<<n-dep[root]+1)-1ll;
    int res=0;
    if(tire[root][0]) res+=query2(tire[root][0],top);
    if(tire[root][1]) res+=query2(tire[root][1],top);
    return res;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    f[1]=(1ll<<n)-1ll,p[1]=true,insert(1);
    for(;m--;)
    {
        int o,u;
        cin>>o>>u;
        if(o==1)
        {
            if(!p[u])
            {
                int up=query(u),cnt=0,pos=insert(u);
                p[u]=true;
                for(int j=u;j;j>>=1) cnt++;
                f[pos]=(1ll<<n-cnt+1)-1ll-query2(pos,pos),f[up]-=f[pos];
                // cout<<pos<<' '<<query2(pos,pos)<<endl;
            }
        }
        else
        {
            // cout<<query(u)<<' ';
            // cout<<f[query(u)]<<'\n';
            ans^=f[query(u)];
        }
    }
    cout<<ans;
    return 0;
}