[BZOJ3784]树上的路径（点分治+dfs序+st表+堆）

2019-11-08 19:47:03

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

这道题并不是像普通的点分一样现在根上加然后在儿子上把不合法的减去，而是直接只能查询合法的，这种思维定式要改一改了。。。刚开始一直在往这方面考虑。。直到看到有人说这道题和超级钢琴那道题很像才受到启发yy出这种不靠谱的的做法。。。

首先从当前根出发到每一个点都求出了一条路径，那么怎么组合是合法的呢？就是路径的两个端点不能在根的同一个儿子里是否在同一个儿子里可以用dfs序来区分，那么标记dfs序之后，每一个点能匹配的点就得到了一段连续的区间如果直接将其展成序列的话，也就等价于每一个点对应一段合法的区间，然后求前m大这就已经变成超级钢琴那道题了首先对于每一个点将其区间内的最大值求出，然后压到堆里。每从堆中弹出一个点就将其对应的区间[l,loc-1][loc+1,r]都加进堆里，这样不断地弹m次就行了时间复杂度O(nlogn+mlogk) $O(nlogn+mlogk)$ ，k为堆的大小，反正我写得挺卡的。。。

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<queue>using namespace std;#define N 50005#define sz 20struct Point{int deep,l,r;};struct rmq{ int val,loc; rmq(int VAL=0,int LOC=0) { val=VAL,loc=LOC; }};struct heap{ int val,id,l,r,loc; heap(int VAL=0,int ID=0,int L=0,int R=0,int LOC=0) { val=VAL,id=ID,l=L,r=R,loc=LOC; } bool Operator < (const heap &a) const { return a.val>val; }};int n,m,x,y,z,sum,root,dfs_clock,last;int tot,point[N],nxt[N*2],v[N*2],c[N*2];int big[N],size[N],d[N],in[N],out[N],trans[N],lg[N];int ans[N*sz];bool vis[N];Point pt[N*sz];rmq st[N*sz][sz];PRiority_queue <heap> q;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){ trans[++trans[0]]=x; in[x]=++dfs_clock; 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); } out[x]=dfs_clock;}void redfs(int rt,int x,int fa){ if (x!=rt) out[x]=out[fa]; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&!vis[v[i]]) redfs(rt,v[i],x);}void dfs(int x){ vis[x]=1; last=dfs_clock; d[x]=0;in[x]=out[x]=++dfs_clock; trans[trans[0]=1]=x; for (int i=point[x];i;i=nxt[i]) if (!vis[v[i]]) { d[v[i]]=c[i]; getdeep(v[i],0); } for (int i=point[x];i;i=nxt[i]) if (!vis[v[i]]) redfs(v[i],v[i],0); for (int i=1;i<=trans[0];++i) { int now=trans[i]; pt[in[now]].deep=d[now]; pt[in[now]].l=out[now]+1,pt[in[now]].r=dfs_clock; } for (int i=point[x];i;i=nxt[i]) if (!vis[v[i]]) { sum=size[v[i]];root=0; getroot(v[i],0); dfs(root); }}void init(){ for (int i=1,p=0;i<=n;++i) { while ((1<<p)<=i) ++p; lg[i]=p-1; } for (int i=1;i<=n;++i) st[i][0].val=pt[i].deep,st[i][0].loc=i; for (int j=1;j<sz;++j) for (int i=1;i<=n;++i) if (i+(1<<j)-1<=n) { if (st[i][j-1].val>=st[i+(1<<(j-1))][j-1].val) st[i][j]=st[i][j-1]; else st[i][j]=st[i+(1<<(j-1))][j-1]; }}rmq query(int l,int r){ if (l>r) return rmq(0,0); int k=lg[r-l+1]; if (st[l][k].val>=st[r-(1<<k)+1][k].val) return st[l][k]; else return st[r-(1<<k)+1][k];}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); } big[0]=N; sum=n;root=0; getroot(1,0); dfs(root); n=dfs_clock;init(); rmq Max; for (int i=1;i<=n;++i) if (pt[i].l<=pt[i].r) { Max=query(pt[i].l,pt[i].r); q.push(heap(Max.val+pt[i].deep,i,pt[i].l,pt[i].r,Max.loc)); } for (int i=1;i<=m;++i) { heap now=q.top();q.pop(); printf("%d/n",now.val); if (now.l<=now.loc-1) { Max=query(now.l,now.loc-1); q.push(heap(Max.val+pt[now.id].deep,now.id,now.l,now.loc-1,Max.loc)); } if (now.loc+1<=now.r) { Max=query(now.loc+1,now.r); q.push(heap(Max.val+pt[now.id].deep,now.id,now.loc+1,now.r,Max.loc)); } } return 0;}

上一篇：历届试题兰顿蚂蚁

下一篇：Uva208 Firetruck【dfs】【习题7-1】