bzoj 3219: 巡游 （点分治+单调队列+二分）

题目描述

传送门

题目大意： 找出一条长度[l,r]的中位数最大的路径。

题解

二分中位数的权值，然后将边权小于mid赋值成-1，大于等于mid赋值成1，如果存在一条长度为l,r且路径权值和>=0的路径则说明当前答案可行。具体的做法与重建计划类似。 时限比较的卡，有几点需要注意。 （1）把每次点分的树根都预处理出来，就不用每次都找了。 （2）对于每个点来说，计算答案的时候我们优先就算深度较浅的子树。 （3）统计某棵子树的时候用bfs，边统计边判断是否有可行的答案，找到后直接退出。

代码

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define N 200003 #define inf 1000000000 using namespace std; struct data{ int x,fa,len,dep; data(int X=0,int F=0,int Len=0,int D=0){ x=X,fa=F,len=Len,dep=D; } }a[N]; int head,tail,head1,tail1,L,R,n,tot,val,ans,mx,cnt,lc[N],son[N],deep[N],fa[N],dep[N],len[N]; int point[N],nxt[N],v[N],c[N],f[N],g[N],size[N],vis[N],root,m,sz,b[N],st[N],top,p[N],q[N]; void add(int x,int y,int z) { tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z; tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; c[tot]=z; } void getroot(int x,int fa) { size[x]=1; f[x]=0; for (int i=point[x];i;i=nxt[i]){ if (vis[v[i]]||v[i]==fa) continue; getroot(v[i],x); size[x]+=size[v[i]]; f[x]=max(f[x],size[v[i]]); } f[x]=max(f[x],m-size[x]); if (f[x]<f[root]) root=x; } bool check(int x,int mid) { val=mid; g[0]=0; int rr=0; for (int i=1;i<=R;i++) g[i]=-inf; for (int i=point[x];i;i=nxt[i]) { if (vis[v[i]]) continue; int s=0; int t=1; head=1,tail=0; for (int j=rr;j>=L;j--) { while (head<=tail&&g[q[tail]]<=g[j]) tail--; q[++tail]=j; } fa[p[1]=v[i]]=x; dep[v[i]]=1; len[v[i]]=(c[i]>=val?1:-1); while (s<t) { s++; while (head<=tail&&q[head]+dep[p[s]]>R) head++; if (dep[p[s]]<=L) { while (head<=tail&&g[q[tail]]<=g[L-dep[p[s]]]) tail--; q[++tail]=L-dep[p[s]]; } if (head<=tail&&g[q[head]]+len[p[s]]>=0) return 1; if (dep[p[s]]>=R) continue; for (int j=point[p[s]];j;j=nxt[j]) if (!vis[v[j]]&&v[j]!=fa[p[s]]) { fa[p[++t]=v[j]]=p[s]; dep[v[j]]=dep[p[s]]+1; len[v[j]]=len[p[s]]+(c[j]>=val?1:-1); } } rr=max(rr,dep[p[t]]); for (int j=1;j<=t;j++) g[dep[p[j]]]=max(g[dep[p[j]]],len[p[j]]); } return false; } int cmp(int x,int y) { return deep[x]<deep[y]; } int get_deep(int x,int fa,int dep) { int Max=0; if (dep==R) return R; for (int i=point[x];i;i=nxt[i]){ if (vis[v[i]]||v[i]==fa) continue; Max=max(Max,get_deep(v[i],x,dep+1)); if (Max==R) return R; } return dep; } void dfs(int x) { vis[x]=1; st[++top]=x; int tk=0; for (int i=point[x];i;i=nxt[i]) { if (vis[v[i]]||size[v[i]]<L) continue; deep[son[++tk]=v[i]]=get_deep(v[i],x,1); lc[son[tk]]=c[i]; } sort(son+1,son+tk+1,cmp); tk=0; for (int i=point[x];i;i=nxt[i]){ if (vis[v[i]]||size[v[i]]<L) continue; v[i]=son[++tk],c[i]=lc[son[tk]]; } for (int i=point[x];i;i=nxt[i]){ if (vis[v[i]]||size[v[i]]<L) continue; root=0; m=size[v[i]]; getroot(v[i],x); dfs(root); } } bool pd(int mid) { for (int i=1;i<=n;i++) vis[i]=0; for (int i=1;i<=top;i++) { vis[st[i]]=1; if (check(st[i],mid)) return true; } return false; } int main() { freopen("a.in","r",stdin); freopen("my.out","w",stdout); scanf("%d%d%d",&n,&L,&R); for (int i=1;i<n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); mx=max(mx,z); b[i]=z; } sort(b+1,b+n); ans=-1; sz=unique(b+1,b+n)-b-1; root=0; m=n; f[0]=inf; getroot(1,0); dfs(root); int l=1; int r=sz; while (l<=r) { int mid=(l+r)/2; if (pd(b[mid])) ans=max(ans,b[mid]),l=mid+1; else r=mid-1; } printf("%d\n",ans); }