【MYCOI R1】那猫猫城的集市 题解

· · 题解

此题解由用户 @tanghg 撰写，@WangBX 添加部分内容。

本题为保证卡掉 O(n\log^2n) 的做法，轻微卡常，谢罪。

Subtask 1，2

考虑直接暴力模拟即可。

Subtask 3

可以证明答案此时只与 dis(u,v) 的奇偶性有关。

Subtask 4

相当于序列，可以使用可持久化线段树等数据结构维护。

Subtask 5，6

我们考虑对询问进行优化。由 Subtask 3 对我们的启示，我们先考虑将一个询问 (u,v,x) 拆成 (u,l) 和 (l,v) 两个部分（其中 l 指 u,v 的 lca）考虑。

但是这样我们发现好像还是不太好做，因为拆到 l 之后从上方到根的那段不是很好处理。

我们不妨假设 x 在 (u,l) 中会被交换，否则直接无意义不考虑。那么我们考虑将这个询问拆成 (u,1) 和 (1,l)。这样我们发现这个询问等同于从 u 开始一直换到 l 的下一层，没有换 l。

那么对于 (l,v) 同理拆成 (f_l,1) 和 (1,v)，发现这样子拆分的话也是完全等价的。

那么我们现在就将所有询问拆成了 2 个从根到某个节点和从某个节点到根的询问。

那么对于从根到某个节点是较为容易的。我们直接模拟维护一个置换即可，然后离线下来直接在过程中处理。

对于从某个节点到根，我们维护一下这个点会在最近的哪里开始第一次交换，直接用一个栈维护。那么之后我们就类比 Subtask 3，提前预处理出这个节点的两个值在交换后会最终在根换成什么即可。

:::info[更严谨的表述]{open}

我们定义 f_u(x) 表示 u 节点处的变换，即

f_u(x)=\begin{cases}a_u&\text{if } x=b_u\\b_u&\text{if }x=a_u\\x&\text{otherwise}\end{cases}

定义 f^\prime_u 表示 f_u 的反函数，容易发现 f_u(f_u(x))=x，即 f^\prime_u=f_u。

那么一个询问 u,v,x 可以被刻画为 f_v(f_{fa_v}(\cdots f_l(\cdots(f_{fa_u}(f_u(x)))\cdots)\cdots))=(f_v\circ f_{fa_v}\circ\cdots\circ f_l\circ\cdots f_{fa_u}\circ f_u)(x)。

其中 \circ 表示函数的复合。

考虑一个类似于树上差分的东西，定义 g_u=f_u\circ f_{fa_u}\circ f_{fa_{fa_u}}\circ\cdots\circ f_{root}。

定义 g^\prime_u 表示 g_u 的反函数，则 g^\prime_u=f^\prime_{root}\circ\cdots\circ f^\prime_{fa_u}\circ f^\prime_u=f_{root}\circ\cdots\circ f_{fa_u}\circ f_u。

设 l 的儿子中 k 为 u 的父亲（也就是 u\to l 路径中倒数第二个点） ，则有：

\begin{aligned} ans&=(f_v\circ f_{fa_v}\circ\cdots\circ f_l\circ f_k\circ\cdots f_{fa_u}\circ f_u)(x)\\ &=\left[(f_v\circ f_{fa_v}\circ\cdots\circ f_l)\circ(f_k\circ\cdots f_{fa_u}\circ f_u)\right](x)\\ &=\left[(f_v\circ f_{fa_v}\circ\cdots\circ f_l\circ f_{fa_l}\circ\cdots\circ f_{root}\circ f^\prime_{root}\circ\cdots\circ f^\prime_{fa_l})\circ(f_l\circ f_{fa_l}\circ\cdots\circ f_{root}\circ f_{root}^\prime\circ\cdots\circ f^\prime_{fa_l}\circ f^\prime_l\circ f_k\circ\cdots f_{fa_u}\circ f_u)(x)\right]\\ &=\left[(f_v\circ f_{fa_v}\circ\cdots\circ f_l\circ f_{fa_l}\circ\cdots\circ f_{root}\circ f_{root}\circ\cdots\circ f_{fa_l})\circ(f_l\circ f_{fa_l}\circ\cdots\circ f_{root}\circ f_{root}\circ\cdots\circ f_{fa_l}\circ f_l\circ f_k\circ\cdots f_{fa_u}\circ f_u)\right](x)\\ &=\left[(g_v\circ g^\prime_{fa_l})\circ(g_l\circ g^\prime_u)\right](x)\\ &=(g_v\circ g^\prime_{fa_l}\circ g_l\circ g^\prime_u)(x)\\ \end{aligned}

这样，我们就把每个询问拆成了四步。注意 \circ 运算是从右向左结合的。

我们可以将询问离线，做四次 dfs，每次 dfs 把询问挂上点，dfs 过程中维护 g_u 和 g^\prime_u，整体处理一步操作。

:::

时间复杂度 O(n\log n)，瓶颈在 lca，但可以结合 Tarjan lca 做到 O(n)。但是出题人并没有刻意卡掉这个部分。

:::info[4 次 dfs 的代码]

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
typedef long long ll;
const int MAXN=1e6+5;
namespace io
{
    ...
}
int n,Q,a[MAXN],b[MAXN];
vector<int>adj[MAXN];
struct Query{
    int u,v,x;
}q[MAXN];
int st[MAXN][21],dfn[MAXN],dfntot;
int p[MAXN],up[MAXN][2];
stack<int>sta[MAXN];
vector<int>qn[MAXN];
int id[MAXN];
void dfs_init(int u,int f){
    st[++dfntot][0]=f;
    dfn[u]=dfntot;
    swap(p[a[u]],p[b[u]]);
    up[u][0]=p[a[u]];
    up[u][1]=p[b[u]];
    for(auto v:adj[u]){
        if(v==f){
            continue;
        }
        dfs_init(v,u);
    }
    swap(p[a[u]],p[b[u]]);
}
void dfs_down(int u){
    swap(id[a[u]],id[b[u]]);
    swap(p[id[a[u]]],p[id[b[u]]]);
    for(auto i:qn[u]){
        q[i].x=p[q[i].x];
    }
    for(auto v:adj[u]){
        if(v==st[dfn[u]][0]){
            continue;
        }
        dfs_down(v);
    }
    swap(id[a[u]],id[b[u]]);
    swap(p[id[a[u]]],p[id[b[u]]]);
}
void dfs_up(int u){
    sta[a[u]].push(u);
    sta[b[u]].push(u);
    for(auto i:qn[u]){
        if(!sta[q[i].x].empty()){
            if(a[sta[q[i].x].top()]==q[i].x){
                q[i].x=up[sta[q[i].x].top()][0];
            }else{
                q[i].x=up[sta[q[i].x].top()][1];
            }
        }
    }
    for(auto v:adj[u]){
        if(v==st[dfn[u]][0]){
            continue;
        }
        dfs_up(v);
    }
    sta[a[u]].pop();
    sta[b[u]].pop();
}
void clear(){
    rep(i,1,n){
        qn[i].clear();
    }
}
#define gin(u,v) (dfn[u]<dfn[v]?u:v)
int lca(int u,int v){
    if(u==v){return u;}
    if(dfn[u]>dfn[v]){swap(u,v);}
    u=dfn[u]+1,v=dfn[v];
    int g=__lg(v-u+1);
    return gin(st[u][g],st[v-(1<<g)+1][g]);
}
using namespace io;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    read(n);
    read(Q);
    rep(i,1,n){
        read(a[i]);
        p[i]=i;
        id[i]=i;
    }
    rep(i,1,n){
        read(b[i]);
    }
    rep(i,1,n-1){
        int u,v;
        read(u);
        read(v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs_init(1,0);
    int up=__lg(n);
    rep(j,1,up){
        rep(i,1,n-(1<<j)+1){
            st[i][j]=gin(st[i][j-1],st[i+(1<<(j-1))][j-1]);
        }
    }
    rep(i,1,Q){
        read(q[i].u);
        read(q[i].v);
        read(q[i].x);
    }
    rep(i,1,Q){
        qn[q[i].u].push_back(i);
    }
    dfs_up(1);
    clear();
    rep(i,1,Q){
        qn[lca(q[i].u,q[i].v)].push_back(i);
    }
    dfs_down(1);
    clear();
    rep(i,1,Q){
        qn[st[dfn[lca(q[i].u,q[i].v)]][0]].push_back(i);
    }
    dfs_up(1);
    clear();
    rep(i,1,Q){
        qn[q[i].v].push_back(i);
    }
    dfs_down(1);
    rep(i,1,Q){
        cout<<q[i].x<<"\n";
    }
    return 0;
}

:::

还有一个比较妙的小常数优化：我们发现上一步得到的式子是 ans=(g_v\circ g^\prime_{fa_l}\circ g_l\circ g^\prime_u)(x)，其中 g^\prime_{fa_l}\circ g_l 只和 l 有关，因此将对应的两次 dfs 合并，即可在 3 次 dfs 内解决问题。

关于卡常：本题略微卡常，但是只要加上快读、3 次 dfs、tarjan lca 中的任何 2 个优化即可大概率通过，加上全部即可稳定通过。

最终 std 如下，复杂度 O(n\alpha(n))，最慢点只有 1.66s。

#include<iostream>
#include<vector>
using namespace std;
struct query { int u,v,lca,x; query(){} query(int u,int v,int lca,int x):u(u),v(v),lca(lca),x(x){} };
namespace io
{
    char *p1,*p2,buf[100001];
    #define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
    template<typename T>
    inline typename __gnu_cxx::__enable_if<__is_integer<T>::__value,T>::__type read()
    {
        T sum=0;
        char ch;
        do ch=getchar();                               while(!isdigit(ch));
        do sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar(); while( isdigit(ch));
        return sum;
    }
    template<typename T>
    inline typename __gnu_cxx::__enable_if<__is_integer<T>::__value,void>::__type read(T& sum)
    {
        sum=0;
        char ch;
        do ch=getchar();                               while(!isdigit(ch));
        do sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar(); while( isdigit(ch));
    }
    #undef getchar
}
using namespace io;
const int MAXN = 1000005;
const int MAXE = 2000005;
const int MAXQ = 1000005;

int head[MAXN], to[MAXE], nxt[MAXE], ecnt=0;
inline void add_edge(int u,int v){ to[++ecnt]=v; nxt[ecnt]=head[u]; head[u]=ecnt; }

int qu_head[MAXN], qu_to[2*MAXQ], qu_id[2*MAXQ], qu_nxt[2*MAXQ], qecnt=0;
inline void add_qu(int u,int v,int id){ qu_to[++qecnt]=v; qu_id[qecnt]=id; qu_nxt[qecnt]=qu_head[u]; qu_head[u]=qecnt; }

int d1_head[MAXN], d1_nxt[MAXQ];
int d2_head[MAXN], d2_nxt[MAXQ];
int d3_head[MAXN], d3_nxt[MAXQ];
inline void add_d1(int u,int id){ d1_nxt[id]=d1_head[u]; d1_head[u]=id; }
inline void add_d2(int u,int id){ d2_nxt[id]=d2_head[u]; d2_head[u]=id; }
inline void add_d3(int u,int id){ d3_nxt[id]=d3_head[u]; d3_head[u]=id; }

int p[MAXN],rp[MAXN];
int a[MAXN],b[MAXN];
int n,m;
query q[MAXQ];
int uf[MAXN],anc[MAXN];
bool vis[MAXN];

int findf(int x){return uf[x]==x?x:uf[x]=findf(uf[x]);}
void unite(int x,int y){x=findf(x);y=findf(y);if(x!=y)uf[y]=x;}
void tarjan(int u,int f)
{
    uf[u]=u; anc[u]=u;
    for(int ei=head[u]; ei; ei=nxt[ei]){
        int v=to[ei]; if(v==f) continue;
        tarjan(v,u);
        unite(u,v);
        anc[findf(u)]=u;
    }
    vis[u]=1;
    for(int qi=qu_head[u]; qi; qi=qu_nxt[qi]){
        int v=qu_to[qi], id=qu_id[qi];
        if(vis[v]) q[id].lca=anc[findf(v)];
    }
}
// removed binary-lifting dfs/lca to reduce memory; Tarjan offline LCA used instead
void dfs1(int u,int f)
{
    swap(rp[p[a[u]]],rp[p[b[u]]]);
    swap(p[a[u]],p[b[u]]);
    for(int qq=d1_head[u]; qq; qq=d1_nxt[qq]){ int id=qq; q[id].x = p[q[id].x]; add_d2(q[id].lca, id); }
    for(int ei=head[u]; ei; ei=nxt[ei]){ int v=to[ei]; if(v!=f) dfs1(v,u); }
    swap(p[a[u]],p[b[u]]);
    swap(rp[p[a[u]]],rp[p[b[u]]]);
}
void dfs2(int u,int f)
{
    for(int qq=d2_head[u]; qq; qq=d2_nxt[qq]){ int id=qq; q[id].x = rp[q[id].x]; }
    swap(rp[p[a[u]]],rp[p[b[u]]]);
    swap(p[a[u]],p[b[u]]);
    for(int qq=d2_head[u]; qq; qq=d2_nxt[qq]){ int id=qq; q[id].x = p[q[id].x]; add_d3(q[id].v, id); }
    for(int ei=head[u]; ei; ei=nxt[ei]){ int v=to[ei]; if(v!=f) dfs2(v,u); }
    swap(p[a[u]],p[b[u]]);
    swap(rp[p[a[u]]],rp[p[b[u]]]);
}
void dfs3(int u,int f)
{
    swap(rp[p[a[u]]],rp[p[b[u]]]);
    swap(p[a[u]],p[b[u]]);
    for(int qq=d3_head[u]; qq; qq=d3_nxt[qq]){ int id=qq; q[id].x = rp[q[id].x]; }
    for(int ei=head[u]; ei; ei=nxt[ei]){ int v=to[ei]; if(v!=f) dfs3(v,u); }
    swap(p[a[u]],p[b[u]]);
    swap(rp[p[a[u]]],rp[p[b[u]]]);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    read(n),read(m);
    for(int i=1;i<=n;i++)   read(a[i]);
    for(int i=1;i<=n;i++)   read(b[i]);
    for(int i=1,u,v;i<n;i++)    { read(u),read(v); add_edge(u,v); add_edge(v,u); }
    for(int i=1,u,v,x;i<=m;i++){
        read(u),read(v),read(x);
        q[i]=query(u,v,0,x);
        add_qu(u,v,i);
        add_qu(v,u,i);
    }
    tarjan(1,0);
    for(int i=1;i<=m;i++) add_d1(q[i].u,i);
    for(int i=1;i<=n;i++)   p[i]=rp[i]=i;
    dfs1(1,0);
    dfs2(1,0);
    dfs3(1,0);
    for(int i=1;i<=m;i++)   cout<<q[i].x<<"\n";
}