题解：P16596 【四川省集】仙人掌最小值查询

· · 题解

这是一个高一了还不会省选 D1T1 的菜鸟在 SC 省集的场上做法。
前面的转化我就不讲了，可以看看别的题解。
前缀线性基是啥，我不会啊，这也太难了。
我只会 O(\log^2V) 合并线性基，和 O(\log V) 插入啊，这咋办啊。
考虑将线性基看做一个黑盒其支持 O(\log^2 V) 合并和 O(\log V) 插入单点。
我们考虑随机撒 B 个点树分块之后建虚树。
首先可以通过遍历相邻两个关键点间的所有点，把这个点插入虚树上这条边的线性基中。
这一步复杂度 O(n\log V)。
然后对每个关键点遍历虚树，求出到其他所有关键点的线性基。
这一步可以每次合并一条边上的线性基做到 O(B^2\log^2 V)。
然后考虑询问，每次找到询问的链上的最靠外的两个关键点，拿出他们之间的线性基，然后把链上剩余的点暴力插入。
由于经典结论，每个点到最近关键点的期望距离是 O(\dfrac nB)，所以这一步的复杂度就是 O(\dfrac{nk\log V}{B})。
尝试平衡复杂度。
有当 B^2\log^2 V=\dfrac{nk\log V}{B} 即 B=(\dfrac{nk}{\log V})^{\frac 13} 时复杂度最优。
为 O(n^{\frac 23}k^{\frac 23}\log^{\frac 43}V)。
:::info[你可能需要的卡常小妙招。]
圆方树的方点是不必要的，事实上，随便定根之后把每个圆点的方儿子的儿子变成这个圆点的儿子，然后把这个方点的权值挂在这些边上，答案依然正确。 ::: :::info[代码。]

#include<bits/stdc++.h>
using namespace std;

int n,m,k,B,siz[500001],h[500001],F[500001],Fw[500001],vis[500001],ir[500001],key[500001],cnt,tot[500001],Fb[500001],Fib[500001],fa[21][500001],dfn[500001],cntdfn;
pair<int,int>W[500001];
vector<array<int,3>>Map[500001],son[500001];
mt19937 rnd(clock());

struct My
{
    int tot,w[31];
    My(){tot=0;for(int i=0;i<31;i++)w[i]=0;}
    void insert(int x)
    {
        if(tot==30)
            return;
        for(int i=29;~i&&x;i--)
            if((x>>i)&1)
            {
                if(w[i])
                    x^=w[i];
                else
                {
                    ++tot;
                    w[i]=x;
                    return;
                }
            }
    }
}M[1301][1301];
vector<int>vec;
vector<pair<int,My>>Mb[500001];
My disbf[500001],disbnf[500001];

My merge(My x,My y)
{
    My ans=x;
    for(int i=0;i<30;i++)
        if(y.w[i])
            ans.insert(y.w[i]);
    return ans;
}

void dfs(int u,int f,int fe)
{
    vec.push_back(u);
    vis[u]=1;
    h[u]=h[f]+1;
    for(auto&[v,w,e]:Map[u])
    {
        if(e==fe)
            continue;
        if(vis[v]&&h[v]<h[u])
        {
            vector<int>tmp;
            int p=vec.size()-1;
            while(vec[p]!=v)
                tmp.push_back(vec[p--]);
            tmp.push_back(v);
            for(int x:tmp)
                if(x!=v)
                    F[x]=v;
            int val=Fw[u]^Fw[v]^w;
            for(int x:tmp)
                if(x!=v)
                    ir[x]=1,
                    W[x]={Fw[x]^Fw[v],val},
                    son[v].push_back({x,Fw[x]^Fw[v],val}),
                    son[x].push_back({v,Fw[x]^Fw[v],val});
            continue;
        }
        if(vis[v])
            continue;
        Fw[v]=Fw[u]^w;
        dfs(v,u,e);
        if(!ir[v])
            F[v]=u,
            W[v]={w,0},
            son[u].push_back({v,w,0}),
            son[v].push_back({u,w,0});
    }
    vec.pop_back();
}

int bf(int u,int v)
{
    int val=0;
    My vec;
    while(u!=v)
    {
        if(h[u]<h[v])
            swap(u,v);
        val^=W[u].first;
        vec.insert(W[u].second);
        u=F[u];
    }
    for(int i=29;~i;i--)
        if(((val>>i)&1)&&vec.w[i])
            val^=vec.w[i];
    return val;
}

void dfs1(int u,int f)
{
    h[u]=h[f]+1;
    for(auto&[v,a,b]:son[u])
        if(v!=f)
            Fw[v]=Fw[u]^a,
            dfs1(v,u),
            tot[u]+=tot[v];
    if(!key[u]&&tot[u]>1)
        key[u]=++cnt;
    if(key[u])
        tot[u]=1;
}

void dfs2(int u,int f)
{
    if(key[u])
        Fb[u]=u;
    for(auto&[v,a,b]:son[u])
        if(v!=f)
            Fb[v]=Fb[u],
            dfs2(v,u);
}

void solve(int u,int f,int x,My now)
{
    if(u!=x&&key[u])
    {
        Mb[x].push_back({u,now});
        return;
    }
    if(x==Fb[u])
        disbf[u]=now;
    else
        Fib[u]=x,
        disbnf[u]=now;
    for(auto&[v,a,b]:son[u])
        if(v!=f)
        {
            auto p=now;
            p.insert(b);
            solve(v,u,x,p);
        }
}

void Do(int u,int f,int x,My now)
{
    M[key[x]][key[u]]=now;
    for(auto&[v,w]:Mb[u])
        if(v!=f)
            Do(v,u,x,merge(now,w));
}

void getdfn(int u,int f)
{
    dfn[u]=++cntdfn;
    siz[u]=1;
    for(auto&[v,w]:Mb[u])
        if(v!=f)
            getdfn(v,u),
            siz[u]+=siz[v];
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n>>m>>k;
    B=pow(n*1ll*k/30.l,1./3)/4+1;
    vector<int>vec;
    for(int i=1;i<=n;i++)
        vec.push_back(i);
    shuffle(vec.begin()+1,vec.end(),rnd);
    for(int i=1;i<=B;i++)
        key[vec[i-1]]=i;
    cnt=B;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        if(u==v)
            continue;
        Map[u].push_back({v,w,i});
        Map[v].push_back({u,w,i});
    }
    dfs(1,0,0);
    Fw[1]=0;
    dfs1(1,0);
    dfs2(1,0);
    for(int i=1;i<=n;i++)
        if(key[i])
            solve(i,0,i,My());
    for(int i=1;i<=n;i++)
        if(key[i])
            Fb[i]=Fib[i]=i,
            Do(i,0,i,My());
    getdfn(1,0);
    while(k--)
    {
        int u,v;
        cin>>u>>v;
        if(Fb[u]==Fb[v])
            cout<<bf(u,v)<<"\n";
        else
        {
            My now;
            int x=Fb[u],y=Fb[v];
            if(dfn[x]>dfn[y])
                swap(u,v),
                swap(x,y);
            int z=Fib[u];
            if(z&&dfn[z]<=dfn[y]&&dfn[y]<dfn[z]+siz[z])
                now=merge(disbf[v],merge(disbnf[u],M[key[z]][key[y]]));
            else
                now=merge(disbf[u],merge(disbf[v],M[key[x]][key[y]]));
            int val=Fw[u]^Fw[v];
            for(int i=29;~i;i--)
                if(((val>>i)&1)&&now.w[i])
                    val^=now.w[i];
            cout<<val<<"\n";
        }
    }
}

:::