[BZOJ3648]寝室管理（点分治+bit）

2019-11-08 19:47:25

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

Sunshine学长去年的互测题orz 然而他给的solution除了点分和bit什么都没说啊。。。硬着头皮想吧，反正我知道要用bit了。。

如果是树的话点分治+二分或者bit就能搞定如果是环套树的话怎么办捏首先考虑不经过环的答案，直接在外向树上点分就行了然后考虑经过环的答案假设当前外向树上深度为h的有x个点，那么上一棵外向树的贡献就是x*深度>=k-1-h的点的个数假设上一个外向树深度为1,2,..的点的个数都加入到bit里，那么就直接在bit里查询就可以了从这里可以想到用bit来维护然后查询，也就是将当前外向树之前的点都加进去，暴力枚举当前外向树的深度，然后查询当然两棵外向树的距离是不一样的，所以在加入的过程中还需要根据距离进行相应的差分，实际上就是后一个加入的深度相比实际深度要比前一个小还有就是因为是一个环，需要展环成链然后做n次细节比较多。。。时间复杂度O(nlogn∗一坨常数) $O(nlogn*一坨常数)$

有一个让我挂挺了的地方，，就是点分治必须每一次更新size，否则找到的重心是不准确的

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<ctime>using namespace std;#define LL long long#define N 200005#define base 200000int n,m,k,x,y;int tot,point[N],nxt[N*2],v[N*2];void addedge(int x,int y){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;}namespace tree{ int sum,root; int big[N],size[N],d[N],deep[N]; bool vis[N]; LL ans; void getroot(int x,int fa) { size[x]=1;big[x]=0; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&!vis[v[i]]) { getroot(v[i],x); size[x]+=size[v[i]]; big[x]=max(big[x],size[v[i]]); } big[x]=max(big[x],sum-size[x]); if (big[x]<big[root]) root=x; } void getdeep(int x,int fa) { deep[++deep[0]]=d[x]; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&!vis[v[i]]) { d[v[i]]=d[x]+1; getdeep(v[i],x); } } int find(int l,int r,int x) { int mid,ans=deep[0]+1; while (l<=r) { mid=(l+r)>>1; if (deep[mid]+x>=k) ans=mid,r=mid-1; else l=mid+1; } return ans; } LL calc(int x,int now) { d[x]=now;deep[0]=0; getdeep(x,0); sort(deep+1,deep+deep[0]+1); LL t=0LL; for (int i=1;i<=deep[0];++i) { int pos=find(i+1,deep[0],deep[i]); t+=(LL)(deep[0]-pos+1); } return t; } void dfs(int x) { ans+=calc(x,0); vis[x]=1; for (int i=point[x];i;i=nxt[i]) if (!vis[v[i]]) { ans-=calc(v[i],1); sum=size[v[i]];root=0; getroot(v[i],0); dfs(root); } } void solve() { big[0]=N; sum=n;root=0; getroot(1,0); dfs(root); PRintf("%lld/n",ans); }}namespace cir_tree{ int sum,root; int h[N],father[N],big[N],size[N],d[N],deep[N]; int c[N*2],trans[N],cnt[N],C[N*2]; bool vis[N],flag; int toth,pth[N],nxth[N*2],vh[N*2],ch[N*2]; LL ans; void findsizeh(int x,int fa) { size[x]=1;h[x]=h[fa]+1; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&!vis[v[i]]) { findsizeh(v[i],x); size[x]+=size[v[i]]; } } void Circle(int x,int y) { memset(vis,0,sizeof(vis)); while (x!=y) { c[++c[0]]=x; x=father[x]; } c[++c[0]]=y; for (int i=1;i<=c[0];++i) vis[c[i]]=1; for (int i=1;i<=c[0];++i) findsizeh(c[i],0); } void findc(int x,int fa) { if (flag) return; vis[x]=1;father[x]=fa; for (int i=point[x];i&&!flag;i=nxt[i]) if (v[i]!=fa) { if (vis[v[i]]) {Circle(x,v[i]);flag=1;return;} findc(v[i],x); } if (flag) return; } void getroot(int x,int fa) { size[x]=1;big[x]=0; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&!vis[v[i]]) { getroot(v[i],x); size[x]+=size[v[i]]; big[x]=max(big[x],size[v[i]]); } big[x]=max(big[x],sum-size[x]); if (big[x]<big[root]) root=x; } void getdeep(int x,int fa) { deep[++deep[0]]=d[x]; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&!vis[v[i]]) { d[v[i]]=d[x]+1; getdeep(v[i],x); } } int find(int l,int r,int x) { int mid,ans=deep[0]+1; while (l<=r) { mid=(l+r)>>1; if (deep[mid]+x>=k) ans=mid,r=mid-1; else l=mid+1; } return ans; } LL calc(int x,int now) { d[x]=now;deep[0]=0; getdeep(x,0); sort(deep+1,deep+deep[0]+1); LL t=0LL; for (int i=1;i<=deep[0];++i) { int pos=find(i+1,deep[0],deep[i]); t+=(LL)(deep[0]-pos+1); } return t; } void dfs(int x) { ans+=calc(x,0); vis[x]=1; for (int i=point[x];i;i=nxt[i]) if (!vis[v[i]]) { ans-=calc(v[i],1); sum=size[v[i]];root=0; getroot(v[i],0); dfs(root); } } void add(int loc,int val) { if (loc<=0) return; for (int i=loc;i<=base+base;i+=i&-i) C[i]+=val; } int query(int loc) { int re=0; if (loc<=0) return re; for (int i=loc;i>=1;i-=i&-i) re+=C[i]; return re; } void sel(int x,int fa) { if (!cnt[h[x]]) trans[++trans[0]]=h[x]; ++cnt[h[x]]; size[x]=1; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&!vis[v[i]]) { sel(v[i],x); size[x]+=size[v[i]]; } } void addh(int x,int y,int z) { ++toth; nxth[toth]=pth[x]; pth[x]=toth; vh[toth]=y; ch[toth]=z; } void solve() { findc(1,0);big[0]=N; for (int i=1;i<=c[0];++i) { vis[c[i]]=0; sum=size[c[i]];root=0; getroot(c[i],0); dfs(root); vis[c[i]]=1; } memset(vis,0,sizeof(vis)); for (int i=1;i<=c[0];++i) vis[c[i]]=1; ++k; memset(C,0,sizeof(C)); for (int i=1;i<=c[0];++i) { trans[0]=0; sel(c[i],0); for (int j=1;j<=trans[0];++j) { addh(c[i],trans[j],cnt[trans[j]]); cnt[trans[j]]=0; } } for (int i=1;i<=c[0];++i) c[i+c[0]]=c[i]; for (int i=1;i<c[0];++i) { for (int j=pth[c[i]];j;j=nxth[j]) add(vh[j]-(i-1)+base,ch[j]); } for (int i=0;i<c[0];++i) { if (i) { for (int j=pth[c[c[0]+i]];j;j=nxth[j]) add(vh[j]-(i-1)+base,-ch[j]); } for (int j=pth[c[c[0]+i]];j;j=nxth[j]) { int qr=n-size[c[c[0]+i]]-query(k-vh[j]-(c[0]+i-1)+base); ans+=(LL)qr*(LL)ch[j]; } for (int j=pth[c[c[0]+i]];j;j=nxth[j]) add(vh[j]-(c[0]+i-1)+base,ch[j]); } printf("%lld/n",ans); }}int main(){ scanf("%d%d%d",&n,&m,&k);--k; for (int i=1;i<=m;++i) { scanf("%d%d",&x,&y); addedge(x,y),addedge(y,x); } if (m==n-1) tree::solve(); else cir_tree::solve();}

上一篇：STL 关联式容器 Set与Map的用法

下一篇：数据结构实验之图论二：基于邻接表的广度优先搜索遍历