[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】