[BZOJ1316]樹上的詢問（點分治+二分）

2019-11-08 02:09:50

字體：大中小

來源：轉載

供稿：網友

題目描述

傳送門

題解

點分治裸題每一次求出deep之后排序然后兩次二分因為點分常數很大做一次求m個比做m次快得多

代碼

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 10005int n,x,y,z,m,sum,root;int q[N],ans[N];int tot,point[N],nxt[N*2],v[N*2],c[N*2];int size[N],big[N],d[N],deep[N];bool vis[N];void add(int x,int y,int z){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z;}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]+c[i]; getdeep(v[i],x); }}int findl(int l,int r,int k){ int ans=0; while (l<=r) { int mid=(l+r)>>1; if (deep[mid]==k) ans=mid,r=mid-1; else if (deep[mid]<k) l=mid+1; else r=mid-1; } return ans;}int findr(int l,int r,int k){ int ans=-1; while (l<=r) { int mid=(l+r)>>1; if (deep[mid]==k) ans=mid,l=mid+1; else if (deep[mid]<k) l=mid+1; else r=mid-1; } return ans;}int calc(int x,int now,int k){ d[x]=now;deep[0]=0; getdeep(x,0); sort(deep+1,deep+deep[0]+1); int t=0; for (int i=1;i<=deep[0];++i) { if (deep[i]+deep[i]>k) break; int l=findl(i,deep[0],k-deep[i]); int r=findr(i,deep[0],k-deep[i]); t+=r-l+1; } return t;}void dfs(int x){ for (int i=1;i<=m;++i) ans[i]+=calc(x,0,q[i]); vis[x]=1; for (int i=point[x];i;i=nxt[i]) if (!vis[v[i]]) { for (int j=1;j<=m;++j) ans[j]-=calc(v[i],c[i],q[j]); sum=size[v[i]];root=0; getroot(v[i],0); dfs(root); }}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<n;++i) { scanf("%d%d%d",&x,&y,&z); add(x,y,z),add(y,x,z); } for (int i=1;i<=m;++i) scanf("%d",&q[i]); big[0]=N; sum=n;root=0; getroot(1,0); dfs(root); for (int i=1;i<=m;++i) if (ans[i]) puts("Yes"); else puts("No");}

上一篇：CAS單點登錄（SSO）介紹及部署

下一篇：猜年齡