目大意给定一棵树每个点上有一个对换 ()σi​(ai​bi​)。q 次询问每次给定 ,,u,v,x。设 →u→v 路径上的点分别是 ,1,2,…,,u,k1​,k2​,…,km​,v求 …1()σv​σkm​​…σk1​​σu​(x)即对路径上对换复合的单点求值。Solution注意到对换的逆就是其自身。尝试用类似树上前缀和的方法去做。拿下面这棵树中 5,7u5,v7 的询问举例。76345()(76)3(45)()(76321123)3(32112345)()(76321)(123)3(321)(12345)()​σ7​σ6​σ3​σ4​σ5​(x)(σ7​σ6​)σ3​(σ4​σ5​)(x)(σ7​σ6​σ3​σ2​σ1​σ1​σ2​σ3​)σ3​(σ3​σ2​σ1​σ1​σ2​σ3​σ4​σ5​)(x)(σ7​σ6​σ3​σ2​σ1​)(σ1​σ2​σ3​)σ3​(σ3​σ2​σ1​)(σ1​σ2​σ3​σ4​σ5​)(x)​这样一来特殊处理 LCA 后我们就拆出了四个前缀对换积可能是左乘也可能是右乘。可以维护一个 n 阶排列表示当前对换积同时维护其逆则左右乘对换均可以做到 (1)O(1)。然后离线下来把询问挂在链的端点四遍 dfs 即可。时间复杂度 (log⁡)O(nlogn)。实现精细的话可以把倍增 LCA 换成 Tarjan做到 (())O(nα(n))。Code#include bits/stdc.h #define rep(i,a,b) for(int i(a);ib;i) #define per(i,a,b) for(int i(a);ib;--i) #define rept(i,a,b) for(int i(a);ib;i) #define pert(i,a,b) for(int i(a);ib;--i) #define eb emplace_back #define pii pairint,int #define il inline #define gc (p1p2(p2(p1buf)fread(buf,1,120,stdin),p1p2)?EOF:*p1) #define pc putchar_unlocked using namespace std; constexpr int N1e65; char *p1,*p2,buf[120]; il void rd(int x){ char c; while((cgc)0||c9); for(xc^48;(cgc)0c9;x(x3)(x1)(c^48)); } il void wr(int x){ x10?pc(x|48):(wr(x/10),pc(x%10|48)); } struct query{ int u,anc,vp,v,x; }q[N]; vectorint g[N],vec[N]; int n,m; int a[N],b[N]; int p[N],inv[N]; int dep[N],fa[20][N],lg[N]; void dfs(int u){ rept(i,1,lg[dep[u]]) fa[i][u]fa[i-1][fa[i-1][u]]; for(int v:g[u]){ if(vfa[0][u]) continue; dep[v]dep[u]1,fa[0][v]u; dfs(v); } } void reset(){ rept(i,1,n){ p[i]inv[i]i; vec[i].clear(); } } il int lca(int u,int v){ if(dep[u]dep[v]) u^v^u^v; int ddep[u]-dep[v]; rept(i,0,lg[d]) if(di1) ufa[i][u]; if(uv) return u; pert(i,lg[dep[u]],0) if(fa[i][u]^fa[i][v]) ufa[i][u],vfa[i][v]; return fa[0][u]; } il void lmul(int a,int b){ int painv[a],pbinv[b]; swap(p[pa],p[pb]),swap(inv[a],inv[b]); } il void rmul(int a,int b){ int pap[a],pbp[b]; swap(p[a],p[b]),swap(inv[pa],inv[pb]); } void solve_r(int u){ rmul(a[u],b[u]); for(int id:vec[u]) q[id].xp[q[id].x]; for(int v:g[u]){ if(vfa[0][u]) continue; solve_r(v); } rmul(a[u],b[u]); } void solve_l(int u){ lmul(a[u],b[u]); for(int id:vec[u]) q[id].xp[q[id].x]; for(int v:g[u]){ if(vfa[0][u]) continue; solve_l(v); } lmul(a[u],b[u]); } signed main(){ rd(n),rd(m); rept(i,1,n) rd(a[i]); rept(i,1,n) rd(b[i]); rep(i,1,n){ int u,v;rd(u),rd(v); g[u].eb(v),g[v].eb(u); } rep(i,2,n) lg[i]lg[i1]1; dfs(1); rept(i,1,m){ rd(q[i].u),rd(q[i].v),rd(q[i].x); q[i].anclca(q[i].u,q[i].v); } reset(); rept(i,1,m) vec[q[i].u].eb(i); solve_r(1); reset(); rept(i,1,m) vec[q[i].anc].eb(i); solve_l(1); rept(i,1,m){ if(q[i].xa[q[i].anc]) q[i].xb[q[i].anc]; else if(q[i].xb[q[i].anc]) q[i].xa[q[i].anc]; } reset(); rept(i,1,m) vec[q[i].anc].eb(i); solve_r(1); reset(); rept(i,1,m) vec[q[i].v].eb(i); solve_l(1); rept(i,1,m) wr(q[i].x),pc(\n); return 0; }