首页 > 代码库 > Tsinsen A1486. 树(王康宁)
Tsinsen A1486. 树(王康宁)
Description
一棵树,问至少有 \(k\) 个黑点的路径最大异或和.
Sol
点分治.
用点分治找重心控制树高就不说了,主要是对答案的统计的地方.
将所有路径按点的个数排序.
可以发现当左端点递增的时候右端点单调递减,时刻满足Trie树里的所有元素都是合法的即可,不断把右端点丢进去,用左端点统计答案.
主要跨越根的时候根的贡献计算了两次,需要删掉一次.
对于需要满足不是一颗子树,可以将Trie树上的节点打一个标记,表示这个节点及其子节点都是在某子树下的路径,子树个数大于1的时候这个标记就没用了.
我在维护标记的时候标记位置打错了...居然有95...调了好长时间QAQ...
Code
#include <bits/stdc++.h>using namespace std;#define debug(a) cout<<#a<<"="<<a<<" "const int N = 1e5+50;const int M = 31;int n,k,kk,rt,ans=-1;int pow2[M];int bl[N],v[N],sz[N],t[N];vector< int > g[N];int usd[N];struct pr { int x,y,z; };bool operator < (const pr &a,const pr &b) { return a.x<b.x; }vector< pr > S;struct Trie { int cnt,rt; int ch[N*M][2],s[N*M],bl[N*M]; int GetNode() { cnt++;ch[cnt][0]=ch[cnt][1]=s[cnt]=0;return cnt; } void init() { cnt=0,rt=GetNode(); } void insert(int x,int fr) { int o=rt,r; for(int i=M-1;~i;i--) { if(x&pow2[i]) r=1;else r=0; if(!ch[o][r]) ch[o][r]=GetNode(),bl[ch[o][r]]=fr; else bl[ch[o][r]]=bl[ch[o][r]]==fr ? fr : 0; o=ch[o][r],s[o]++; } } int getv(int x,int fr) { int o=rt,r,res=0; if(!ch[rt][0] && !ch[rt][1]) return -1; for(int i=M-1;~i;i--) { if(x&pow2[i]) r=1;else r=0; if(s[ch[o][r^1]] && bl[ch[o][r^1]]!=fr) res|=pow2[i],r^=1; if(bl[ch[o][r]]==fr) return -1; o=ch[o][r]; }return res; }}py;inline int in(int x=0,char ch=getchar()) { while(ch>‘9‘ || ch<‘0‘) ch=getchar(); while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();return x; }void GetRoot(int u,int fa,int nn) { t[u]=0,sz[u]=1; for(vector< int >::iterator i=g[u].begin();i!=g[u].end();i++) if((*i)!=fa && !usd[(*i)]) GetRoot(*i,u,nn),t[u]=max(t[u],sz[*i]),sz[u]+=sz[*i]; t[u]=max(t[u],nn-sz[u]); if(t[u]<t[rt]) rt=u;}void GetS(int u,int fa,int c,int vv,int ff) { S.push_back((pr){ c,vv,ff }); if(c>=k) ans=max(ans,vv); for(vector< int >::iterator i=g[u].begin();i!=g[u].end();i++) if((*i)!=fa && !usd[*i]) GetS(*i,u,c+bl[*i],vv^v[*i],ff);}void GetAns(int u,int fa,int nn) { usd[u]=1,py.init(),S.clear();if(bl[u]>=k) ans=max(ans,v[u]); for(vector< int >::iterator i=g[u].begin();i!=g[u].end();i++) if((*i)!=fa && !usd[(*i)]) GetS((*i),u,bl[u]+bl[(*i)],v[(*i)],*i); sort(S.begin(),S.end()); // cout<<u<<" : "<<nn<<endl;// for(int i=0;i<(int)S.size();i++) cout<<S[i].x<<" "<<S[i].y<<" "<<S[i].z<<endl; int lim=S.size(),l=0,r=lim-1; for(;l<lim;l++) { while(l<r && S[l].x+S[r].x>=k+bl[u]) py.insert(S[r].y,S[r].z),r--; ans=max(ans,py.getv(S[l].y^v[u],S[l].z));// debug(l),debug(r),debug(ans)<<endl; }// debug(ans)<<endl;// cout<<"-------------------------"<<endl; int ss; for(vector< int >::iterator i=g[u].begin();i!=g[u].end();i++) if((*i)!=fa && !usd[(*i)]) rt=0,ss=sz[(*i)]>sz[u] ? nn-sz[u] : sz[*i],GetRoot((*i),u,ss),GetAns(rt,rt,ss);}int main() { n=in(),k=in(); for(int i=1;i<=n;i++) bl[i]=in(); for(int i=1;i<=n;i++) v[i]=in(); for(int i=1,u,v;i<n;i++) u=in(),v=in(),g[u].push_back(v),g[v].push_back(u); pow2[0]=1;for(int i=1;i<M;i++) pow2[i]=pow2[i-1]<<1;// for(int i=0;i<M;i++) cout<<pow2[i]<<endl; rt=0,t[rt]=n+1,GetRoot(1,1,n),GetAns(rt,rt,n); cout<<ans<<endl; return 0;}
Tsinsen A1486. 树(王康宁)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。