LG15534 【MYCOI R1】那猫猫城的集市
猫猫城有 \(n\) 个集市，有 \(n-1\) 条双向道路分别连接两个集市，使得任意两个集市可以经过若干条道路到达。每个集市售卖两种货物 \(a_u,b_u(a_u\neq b_u)\)。
现在小咪计划了 \(Q\) 次旅行，每一次小咪会从集市 \(u\) 出发，沿最短路径前往集市 \(v\)。在途径一个集市时（包括 \(u,v\)），小咪会尝试进行交易。如果小咪拥有这个集市售卖的其中一种货物，小咪会将它换成集市中售卖的另一种货物，但如果没有则小咪保留他原来有的货物。
现在一开始小咪拥有一个货物，种类为 \(x\)。求旅行结束后小咪拥有的货物是哪种。
\(n,Q\leq 10^6,1\leq a,b\leq n,x\leq 10^9\)
官方题解链接，写得很详细很推荐，这里只是简单记下笔记。
假设节点 \(u\) 的父亲为 \(fa(u)\)，则原路径经过点，同时每个点都考虑交换
\[u\to fa(u)\to fa(fa(u))\to\cdots lca\to \cdots\to fa(v)\to v
\]
这其实等价于路径
\[[u\to \cdots \to root]\to [root\to \cdots lca]\to [fa(lca)\to\cdots\to root]\to [root\to \cdots\ to v]
\]
为啥，应为对于一种货物 \(x\)，他经过两次同一个节点后，\(x\) 值不变，那么这个路径中相邻且相同的节点就可以被忽略掉，最后等价于原路径。
这样我们求每种货物 \(x\) 从某个节点到根节点变成什么，和从根节点到某个节点变成什么即可。具体实现可以见代码。
#include <bits/stdc++.h>using namespace std;typedef long long ll;
typedef array<int,2>ttfa;
const int N=1000006;
const ll INF=0x3f3f3f3f3f3f3f3f;int n,T;
ttfa a[N];
vector<int>tar[N];//tar 原树int siz[N],dep[N],fat[N],son[N],tps[N];
void dfs1(int u,int f){siz[u]=1;fat[u]=f;dep[u]=dep[f]+1;for(auto v:tar[u]){if(v==f)continue;dfs1(v,u);siz[u]+=siz[v];if(siz[v]>siz[son[u]])son[u]=v;}
}
void dfs2(int u,int t){tps[u]=t;if(son[u])dfs2(son[u],t);for(auto v:tar[u]){if(v==fat[u]||v==son[u])continue;dfs2(v,v);}
}
inline int __lca(int x,int y){while(tps[x]!=tps[y]){if(dep[tps[x]]>dep[tps[y]])swap(x,y);y=fat[tps[y]];}if(dep[x]>dep[y])swap(x,y);return x;
}struct node{int x,y,lca,v,id;
}q[N];
vector<int>qu[N],qd[N];
int las[N],loc[N];void dfsup(int u,int f){swap(las[a[u][0]],las[a[u][1]]);for(auto id:qu[u]){q[id].v=las[q[id].v];}qu[u].clear();for(auto v:tar[u]){if(v==f)continue;dfsup(v,u);}swap(las[a[u][0]],las[a[u][1]]);
}
void dfsdw(int u,int f){int tmp0=loc[a[u][0]],tmp1=loc[a[u][1]];swap(las[tmp0],las[tmp1]);swap(loc[a[u][0]],loc[a[u][1]]);for(auto id:qd[u]){q[id].v=las[q[id].v];}qd[u].clear();for(auto v:tar[u]){if(v==f)continue;dfsdw(v,u);}swap(las[tmp0],las[tmp1]);swap(loc[a[u][0]],loc[a[u][1]]);
}int main(){scanf("%d%d",&n,&T);for(int i=1;i<=n;++i){scanf("%d",&a[i][0]);}for(int i=1;i<=n;++i){scanf("%d",&a[i][1]);}for(int i=1;i<n;++i){int u,v;scanf("%d%d",&u,&v);tar[u].push_back(v);tar[v].push_back(u);}dfs1(1,0);dfs2(1,1);for(int i=1;i<=T;++i){scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].v);q[i].lca=__lca(q[i].x,q[i].y);q[i].id=i;}for(int i=1;i<=n;++i)las[i]=i,loc[i]=i;//1for(int i=1;i<=T;++i){if(q[i].v<=n){qu[q[i].x].push_back(q[i].id);}}dfsup(1,0);//2for(int i=1;i<=T;++i){if(q[i].v<=n){qd[q[i].lca].push_back(q[i].id);}}dfsdw(1,0);//3for(int i=1;i<=T;++i){int f=fat[q[i].lca];if(q[i].v<=n&&f){qu[f].push_back(q[i].id);}}dfsup(1,0);//4for(int i=1;i<=T;++i){if(q[i].v<=n){qd[q[i].y].push_back(q[i].id);}}dfsdw(1,0);for(int i=1;i<=T;++i){printf("%d\n",q[i].v);}puts("");return 0;
}
需要一个求 \(lca\) 的复杂度。