題目描述

給定一個N個結點的樹，結點用正整數1..N編號。每條邊有一個正整數權值。用d(a,b）表示從結點a到結點b路邊上經過邊的權值。其中要求a<b.將這n*(n-1)/2個距離從大到小排序，輸出前M個距離值。

題解

把每次點分治時的dfs序寫下來，假設我們在一個位置找能夠和它拼成一條鏈的另一個位置，可以發現那些位置的順序在dfs序上構成了一段連續區間，用ST表+堆維護。

注意在進隊列之前先內啥一下。

代碼

#include<iostream> #include<cstdio> #include<queue> #include<cmath> #define N 50002 #define M 16 using namespace std; int tot,head[N],lo[N*M],st[M][N*M],size[N],dp[N],sum,now,deep[N],root,n,p[M][N*M]; bool vis[N]; int start,ed; inline int rd(){int x=0;char c=getchar();bool f=0;while(!isdigit(c)){if(c=='-')f=1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return f?-x:x; } struct edge{int n,to,l;}e[N<<1]; inline void add(int u,int v,int l){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;} struct node{int now,l,r,sum;node(int nownum=0,int num1=0,int num2=0){now=nownum;l=num1;r=num2;int loo=lo[r-l+1];sum=now+max(st[loo][l],st[loo][r-(1<<loo)+1]);}int calc(){int loo=lo[r-l+1];if(st[loo][l]>=st[loo][r-(1<<loo)+1])return p[loo][l];else return p[loo][r-(1<<loo)+1];}bool operator <(const node &b)const{return sum<b.sum;} }pa[N*M]; priority_queue<node>q; void getroot(int u,int fa){size[u]=1;dp[u]=0;for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa&&!vis[e[i].to]){int v=e[i].to;getroot(v,u);size[u]+=size[v];dp[u]=max(dp[u],size[v]);}dp[u]=max(dp[u],sum-size[u]);if(dp[u]<dp[root])root=u; } void getsize(int u,int fa){size[u]=1;for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa&&!vis[e[i].to]){int v=e[i].to;getsize(v,u);size[u]+=size[v];} } void getdeep(int u,int fa){st[0][++now]=deep[u];p[0][now]=now;pa[now]=node(deep[u],start,ed);for(int i=head[u];i;i=e[i].n)if(!vis[e[i].to]&&e[i].to!=fa){int v=e[i].to;deep[v]=deep[u]+e[i].l;getdeep(v,u);} } inline void calc(int u){st[0][++now]=0;p[0][now]=now;pa[now]=node{0,now,now};start=now;ed=now;for(int i=head[u];i;i=e[i].n)if(!vis[e[i].to]){int v=e[i].to;deep[v]=e[i].l;getdeep(v,u);ed=now;} } void solve(int u){calc(u);vis[u]=1;for(int i=head[u];i;i=e[i].n)if(!vis[e[i].to]){int v=e[i].to;root=n+1;sum=size[v];getroot(v,u);getsize(root,0);solve(root);} } int main(){n=rd();int k=rd();int u,v,w;for(int i=1;i<n;++i){u=rd();v=rd();w=rd();add(u,v,w);add(v,u,w); }dp[root=n+1]=n+1;sum=n;getroot(1,0);getsize(root,0);solve(root);for(int i=1;(1<<i)<=now&&i<M;++i)for(int j=1;j+(1<<i)-1<=now;++j)st[i][j]=max(st[i-1][j],st[i-1][j+(1<<i-1)]),p[i][j]=st[i-1][j]>=st[i-1][j+(1<<i-1)]?p[i-1][j]:p[i-1][j+(1<<i-1)];for(int i=2;i<=now;++i)lo[i]=lo[i>>1]+1;for(int i=1;i<=now;++i)pa[i]=node(pa[i].now,pa[i].l,pa[i].r),q.push(pa[i]);///care !!!!for(int i=1;i<=k;++i){node x=q.top();q.pop();printf("%d\n",x.sum);int mid=x.calc();if(x.l<mid)q.push(node(x.now,x.l,mid-1));if(x.r>mid)q.push(node(x.now,mid+1,x.r));}return 0; }

轉載于:https://www.cnblogs.com/ZH-comld/p/10426934.html

總結

以上是生活随笔為你收集整理的BZOJ3784树上的路径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。