Loading... ## 前言 本题是简单的、一眼的、普通的、显然的。 ## 正文 ### 0x00 分析题目 > 给定一颗带点权无根树,每次询问给定两个点 $u,v$ 和参数 $k$,回答是否有一个 $u\leftarrow v$ 简单路径的点权子集其异或和是 $k$。 > $n,q\leq 2\times 10^5$ 时间限制为 $6.5$ 秒。 可以肯定的是这个题需要线性基,以及线性基合并等知识,不会的推荐[线性基学习笔记 | Menci's OI Blog](https://oi.men.ci/linear-basis-notes/)。下文默认 $n,q$ 同阶。 ### 0x01 树上倍增 $\mathcal{O}\left(n\log^3{n}\right)$ #### 做法 首先考虑到一个显然的做法,树上倍增,对于每个 $u$ 处理出 $B_{u,k}$ 表示 $u$ 到其 $2^k$ 级祖先这条链的线性基,和普通树上倍增一样只不过合并两个 $2^{k-1}$ 的信息时用线性基合并,则预处理时间复杂度 $\mathcal{O}\left(n\log^3{n}\right)$。 询问时,$u,v$ 不断向上倍增跳,直到其 $lca$ 的位置,这样一共需要合并 $\mathcal{O}\left(\log{n}\right)$ 个线性基,单次询问时间复杂度 $\mathcal{O}\left(\log^3{n}\right)$。 #### 代码实现 实测使用一定的常数优化可以轻松通过: 1. 线性基插入一个数 $x$ 时从 $\log_2 x$ 位开始枚举,每次插入后重新取 $\log_2 x$ 寻找下一位。 2. 树上倍增时从 $\log dep$ 开始倍增。 3. 取 $log_2 x$ 使用 `31^__builtin_clz(x)` 计算最快。 AC CODE,最大点跑了 $6114 ms$。 ```cpp #pragma GCC optimize(3) #pragma GCC target("avx") #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #include<bits/stdc++.h> namespace Fread { const int SIZE = 1 << 21; char buf[SIZE], *S, *T; inline char getchar() { if (S == T) { T = (S = buf) + fread(buf, 1, SIZE, stdin); if (S == T) return '\n'; } return *S++; } } namespace Fwrite { const int SIZE = 1 << 21; char buf[SIZE], *S = buf, *T = buf + SIZE; inline void flush() { fwrite(buf, 1, S - buf, stdout); S = buf; } inline void putchar(char c) { *S++ = c; if (S == T) flush(); } struct NTR { ~ NTR() { flush(); } } ztr; } #ifdef ONLINE_JUDGE #define getchar Fread :: getchar #define putchar Fwrite :: putchar #endif namespace Fastio { struct Reader { template<typename T> Reader& operator >> (T& x) { char c = getchar(); T f = 1; while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } x = 0; while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); } x *= f; return *this; } Reader& operator >> (char& c) { c = getchar(); while (c == ' ' || c == '\n') c = getchar(); return *this; } Reader& operator >> (char* str) { int len = 0; char c = getchar(); while (c == ' ' || c == '\n') c = getchar(); while (c != ' ' && c != '\n' && c != '\r') { // \r\n in windows str[len++] = c; c = getchar(); } str[len] = '\0'; return *this; } Reader(){} } cin; const char endl = '\n'; struct Writer { template<typename T> Writer& operator << (T x) { if (x == 0) { putchar('0'); return *this; } if (x < 0) { putchar('-'); x = -x; } static int sta[45]; int top = 0; while (x) { sta[++top] = x % 10; x /= 10; } while (top) { putchar(sta[top] + '0'); --top; } return *this; } Writer& operator << (char c) { putchar(c); return *this; } Writer& operator << (char* str) { int cur = 0; while (str[cur]) putchar(str[cur++]); return *this; } Writer& operator << (const char* str) { int cur = 0; while (str[cur]) putchar(str[cur++]); return *this; } Writer(){} } cout; } #define cin Fastio :: cin #define cout Fastio :: cout #define endl Fastio :: endl #define ln(x) ((x<=0)?(0):(31^__builtin_clz((x)))) const int NNNN=200001; const int lgN=19; const int W=19; struct LBASE{ int p[W+1]; void insert(register int x){ if(!x) return; register int i; for(i=ln(x);~i;--i) if((x>>i)){ if(p[i]) x^=p[i]; else{ p[i]=x; break; } } } bool isIn(register int x){ register int i; for(i=ln(x);~i;--i) if((x>>i)){ if(p[i]) x^=p[i]; else return false; } return true; } void merge(LBASE &o){ register int i; for(i=W;~i;--i) if(o.p[i]) insert(o.p[i]); return; } void clear(){ register int i; for(i=W;~i;--i) p[i]=0; } }basis[NNNN][lgN],tmp; int par[NNNN][lgN],dep[NNNN],arr[NNNN],maxDep; std::vector<int> e[NNNN]; void addEdge(int u,int v){ e[u].push_back(v); e[v].push_back(u); return; } void dfs(int u,int p){ maxDep=std::max(dep[u]=dep[par[u][0]=p]+1,maxDep); for(auto v:e[u]) if(v!=p) dfs(v,u); } int main(){ #ifndef ONLINE_JUDGE freopen("name.in", "r", stdin); freopen("name.out", "w", stdout); #endif register int i,j,u,v,x,lgDep; int n; cin>>n; for(i=1;i<=n;++i) cin>>arr[i],basis[i][0].insert(arr[i]); for(i=1;i<n;++i){ cin>>u>>v; addEdge(u,v); } dfs(1,0); lgDep=ln(maxDep); for(i=1;i<=lgDep;++i) for(j=1;j<=n;++j) par[j][i]=par[par[j][i-1]][i-1],basis[j][i]=basis[j][i-1],basis[j][i].merge(basis[par[j][i-1]][i-1]); register int q; cin>>q; while(q--){ cin>>u>>v>>x; tmp.clear(); if(dep[u]<dep[v]) std::swap(u,v); for(i=ln(dep[u]-dep[v]);~i;--i) if(dep[par[u][i]]>=dep[v]) tmp.merge(basis[u][i]),u=par[u][i]; if(u!=v){ for(i=ln(dep[u]);~i;--i) if(par[u][i]!=par[v][i]) tmp.merge(basis[u][i]),tmp.merge(basis[v][i]),u=par[u][i],v=par[v][i]; // u=par[0][u]; tmp.insert(arr[par[u][0]]); tmp.insert(arr[u]); tmp.insert(arr[v]); }else tmp.insert(arr[v]); cout<<(tmp.isIn(x)?"YES\n":"NO\n"); } #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; } ``` ### 0x02 点分治做法 $\mathcal{O}\left(n\log^3{n}\right)$ #### 做法 观察发现树上倍增做法之所以慢是应为我们钦定了两个点在他们的 $lca$ 处相遇然后合并线性基,所以需要预处理和查询很多东西。但是对于这个这个题他是无根树,不需要一定在 $lca$ 处才能算。这启发我们使用点分治来处理树上询问。 具体的,对于每次点分治,处理跨越当前子树重心的所有询问。对于每个子树的点 $u$ 处理出其到重心链上的线性基,这一部分不需要线性基合并,只需要直接继承他父亲的线性基然后加入 $u$ 的点权即可。处理查询时合并以 $u$ 到重心的线性基和 $v$ 到重心的线性基即可。单次查询时间复杂度 $\mathcal{O}\left(\log^2{n}\right)$,点分治的时间复杂度 $\mathcal{O}\left(n\log^2{n}\right)$。 思考,点分治的好处是每次查询只需要合并两个线性基,并且预处理不需要合并线性基所以可以得到更优的时间复杂度。 #### 代码实现 加上前面的优化甚至可以跑进一秒。AC CODE: ```cpp #pragma GCC optimize(3) #pragma GCC target("avx") #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #include<bits/stdc++.h> namespace Fread { const int SIZE = 1 << 21; char buf[SIZE], *S, *T; inline char getchar() { if (S == T) { T = (S = buf) + fread(buf, 1, SIZE, stdin); if (S == T) return '\n'; } return *S++; } } namespace Fwrite { const int SIZE = 1 << 21; char buf[SIZE], *S = buf, *T = buf + SIZE; inline void flush() { fwrite(buf, 1, S - buf, stdout); S = buf; } inline void putchar(char c) { *S++ = c; if (S == T) flush(); } struct NTR { ~ NTR() { flush(); } } ztr; } #ifdef ONLINE_JUDGE #define getchar Fread :: getchar #define putchar Fwrite :: putchar #endif namespace Fastio { struct Reader { template<typename T> Reader& operator >> (T& x) { char c = getchar(); T f = 1; while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } x = 0; while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); } x *= f; return *this; } Reader& operator >> (char& c) { c = getchar(); while (c == ' ' || c == '\n') c = getchar(); return *this; } Reader& operator >> (char* str) { int len = 0; char c = getchar(); while (c == ' ' || c == '\n') c = getchar(); while (c != ' ' && c != '\n' && c != '\r') { // \r\n in windows str[len++] = c; c = getchar(); } str[len] = '\0'; return *this; } Reader(){} } cin; const char endl = '\n'; struct Writer { template<typename T> Writer& operator << (T x) { if (x == 0) { putchar('0'); return *this; } if (x < 0) { putchar('-'); x = -x; } static int sta[45]; int top = 0; while (x) { sta[++top] = x % 10; x /= 10; } while (top) { putchar(sta[top] + '0'); --top; } return *this; } Writer& operator << (char c) { putchar(c); return *this; } Writer& operator << (char* str) { int cur = 0; while (str[cur]) putchar(str[cur++]); return *this; } Writer& operator << (const char* str) { int cur = 0; while (str[cur]) putchar(str[cur++]); return *this; } Writer(){} } cout; } #define cin Fastio :: cin #define cout Fastio :: cout #define endl Fastio :: endl #define ln(x) ((x<=0)?(0):(31^__builtin_clz((x)))) const int NNNN=200001; const int lgN=19; const int W=19; struct LBASE{ int p[W+1]; void insert(register int x){ if(!x) return; register int i; for(i=ln(x);x;i=ln(x)) if((x>>i)){ if(p[i]) x^=p[i]; else{ p[i]=x; break; } } } bool isIn(register int x){ register int i; for(i=ln(x);x;i=ln(x)) if((x>>i)){ if(p[i]) x^=p[i]; else return false; } return true; } void merge(LBASE &o){ register int i; for(i=W;~i;--i) if(o.p[i]) insert(o.p[i]); return; } void clear(){ register int i; for(i=W;~i;--i) p[i]=0; } }basis[NNNN],tmp; int arr[NNNN]; std::vector<int> e[NNNN]; void addEdge(int u,int v){ e[u].push_back(v); e[v].push_back(u); return; } struct QRY{ int to,w,id; }; int siz[NNNN],par[NNNN],dep[NNNN]; std::vector<int> cur,viscur; std::vector<QRY> qrys[NNNN]; std::bitset<NNNN> vis,ans,inCur; void dfsInit(int u,int p){ int v; cur.push_back(u); siz[u]=1,par[u]=p; for(auto v:e[u]) if(v!=p&&!vis[v]) dfsInit(v,u),siz[u]+=siz[v]; return; } void dfsCheck(int u,int p){ viscur.push_back(u); basis[u]=basis[p]; basis[u].insert(arr[u]); for(auto v:e[u]) if(v!=p&&!vis[v]) dfsCheck(v,u); return; } void solve(int rt){ register int u,v,newrt=rt,min,tmp; cur.clear(); tmp=0; siz[rt]=1; for(auto v:e[rt]){ if(vis[v]) continue; dfsInit(v,rt); tmp=std::max(tmp,siz[v]); siz[rt]+=siz[v]; } min=tmp; for(auto u:cur){ tmp=siz[rt]-siz[u]; for(auto v:e[u]){ if(vis[v]||par[u]==v) continue; tmp=std::max(tmp,siz[v]); } if(tmp<min){ newrt=u; min=tmp; } } cur.push_back(rt); basis[newrt].clear(); basis[newrt].insert(arr[newrt]); inCur[newrt]=1; for(auto v:e[newrt]){ if(vis[v]) continue; viscur.clear(); dfsCheck(v,newrt); for(auto u:viscur) for(auto qry:qrys[u]) if((!ans[qry.id])&&inCur[qry.to]){ ::tmp=basis[u]; ::tmp.merge(basis[qry.to]); ans[qry.id]=::tmp.isIn(qry.w); } for(auto u:viscur) inCur[u]=1; } for(auto u:cur) inCur[u]=0; vis[newrt]=1; for(auto v:e[newrt]) if(!vis[v]) solve(v); vis[newrt]=0; return; } int main(){ #ifndef ONLINE_JUDGE freopen("name.in", "r", stdin); freopen("name.out", "w", stdout); #endif register int i,j,u,v,x,lgDep; int n; cin>>n; for(i=1;i<=n;++i) cin>>arr[i]; for(i=1;i<n;++i){ cin>>u>>v; addEdge(u,v); } int q; cin>>q; for(i=0;i<q;++i){ cin>>u>>v>>x; qrys[u].push_back((QRY){v,x,i}); qrys[v].push_back((QRY){u,x,i}); if(u==v) ans[i]=((x==arr[u])||(x==0)); } solve(1); for(i=0;i<q;++i) cout<<(ans[i]?"YES\n":"NO\n"); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; } ``` ## 总结 本题利用了点分治对询问优秀的拆分方式解决了本题。 最后修改:2023 年 12 月 06 日 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用,请随意赞赏