[bzoj3784][点分治]树上的路径
程序员文章站
2022-05-08 18:26:44
...
3784: 树上的路径
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 734 Solved: 246
[Submit][Status][Discuss]
Description
给定一个N个结点的树,结点用正整数1..N编号。每条边有一个正整数权值。用d(a,b)表示从结点a到结点b路边上经过边的权值。其中要求a < b.将这n*(n-1)/2个距离从大到小排序,输出前M个距离值。
Input
第一行两个正整数N,M
下面N-1行,每行三个正整数a,b,c(a,b<=N,C<=10000)。表示结点a到结点b有一条权值为c的边。
Output
共M行,如题所述.
Sample Input
5 10
1 2 1
1 3 2
2 4 3
2 5 4
Sample Output
7
7
6
5
4
4
3
3
2
1
HINT
N<=50000,M<=Min(300000,n*(n-1) /2 )
Source
发现是道经典的点分治题目
二分一下路径的长度。就可以知道哪些路径是不合法的。然后把这些路径记录下来,算一下数量。所以效率是nlog^2的,这个效率可以过,但是我们要注意一下常数问题。
有个技巧,如果是二分一下点分治的话,提前记录下root可以有效的提高效率。
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#define edg for(int e=fir[u],v;v=go[e],e;e=nex[e])
using namespace std;
int n,m;
inline int read()
{
char c;
bool flag=false;
while((c=getchar())>'9'||c<'0')
if(c=='-')flag=true;
int res=c-'0';
while((c=getchar())>='0'&&c<='9')
res=(res<<3)+(res<<1)+c-'0';
return flag?-res:res;
}
const int N=50002;
const int M=100002;
int ma,tot,sum,ans,now,root;
int fir[N],nex[M],go[M],val[M],Root[N];
int size[N],Dis[N],dis[N],t[N],Ans[300002];
bool vis[N];
inline void add(int x,int y,int z)
{
nex[++tot]=fir[x];fir[x]=tot;go[tot]=y;val[tot]=z;
nex[++tot]=fir[y];fir[y]=tot;go[tot]=x;val[tot]=z;
}
inline void get_root(int u,int f)
{
int jj=0;
size[u]=1;
edg if(v!=f&&!vis[v])
{
get_root(v,u);
size[u]+=size[v];
jj=jj>size[v]?jj:size[v];
}
jj=jj>sum-size[u]?jj:sum-size[u];
if(jj<ma) ma=jj,root=u;
}
inline void vist(int u)
{
Root[++Root[0]]=u;
vis[u]=1;
get_root(u,0);
edg if(!vis[v])
{
ma=n;
sum=size[v];
get_root(v,u);
vist(root);
}
}
inline void dfs(int u,int f,int va,int x,int flag)
{
if(va>=x)
{
++ans;
if(flag) Ans[++Ans[0]]=va;
}
dis[++dis[0]]=va;
edg if(v!=f&&!vis[v])
dfs(v,u,va+val[e],x,flag);
}
inline bool cmp(int x,int y)
{
return x>y;
}
inline void calc(int x,int flag)
{
int l=Dis[0],r=1,cnt=0;
sort(dis+1,dis+1+dis[0]);
while(((l&&!flag)||flag)&&r<=dis[0])
{
while(l&&Dis[l]+dis[r]>=x) --l;
if(flag)
for(int i=l+1;i<=Dis[0];++i)
Ans[++Ans[0]]=Dis[i]+dis[r];
ans+=Dis[0]-l;
++r;
}
ans+=Dis[0]*(dis[0]-r+1);
l=1;r=1;
while(l<=Dis[0]&&r<=dis[0])
{
while(l<=Dis[0]&&Dis[l]<=dis[r]) t[++cnt]=Dis[l++];
while(r<=dis[0]&&dis[r]<=Dis[l]) t[++cnt]=dis[r++];
}
for(int i=l;i<=Dis[0];++i) t[++cnt]=Dis[i];
for(int i=r;i<=dis[0];++i) t[++cnt]=dis[i];
dis[0]=0;
Dis[0]=cnt;
for(int i=1;i<=cnt;++i) Dis[i]=t[i];
}
inline void solve(int x,int flag)
{
int u;
u=Root[now];
vis[u]=1;
Dis[0]=0;
++now;
edg if(!vis[v])
{
dfs(v,u,val[e],x,flag);
calc(x,flag);
if(ans>=m) return;
}
edg if(!vis[v])
{
solve(x,flag);
if(ans>=m) return;
}
}
inline bool check(int x)
{
ans=0;
now=1;
solve(x,0);
// for(int i=1;i<=n;++i) vis[i]=0;
memset(vis,0,sizeof(vis));
return ans>=m;
}
int main()
{
// freopen("path.in","r",stdin);
// freopen("path.out","w",stdout);
n=read();
m=read();
int x,y,z,l=0,r=0;
for(int i=1;i<n;++i)
{
x=read();
y=read();
z=read();
add(x,y,z);
r+=z;
}
ma=sum=n;
get_root(1,0);
vist(root);
for(int i=1;i<=n;++i) vis[i]=0;
while(l+1<r)
{
int mid=l+r>>1;
if(check(mid)) l=mid;
else r=mid;
}
int fin=(check(r)?r:l)+1;
ma=sum=n;
ans=0;
now=1;
solve(fin,1);
sort(Ans+1,Ans+1+Ans[0],cmp);
for(int i=1;i<=Ans[0];++i)
printf("%d\n",Ans[i]);
for(int i=m-Ans[0];i>=1;--i)
printf("%d\n",fin-1);
}
下一篇: Python简单的网络爬虫刷新博客
推荐阅读
-
洛谷P2664 树上游戏(点分治)
-
数据结构算法分治(两个组的点之间的最小距离)
-
键盘录入一个文件夹路径,统计该文件夹(包含子文件夹)中每种类型的文件及个数,注意:用文件类型(后缀名,不包含.(点),如:"java","txt")作为key, 用个数作为value,放入到map集
-
键盘录入一个文件夹路径,统计该文件夹(包含子文件夹)中每种类型的文件及个数,注意:用文件类型(后缀名,不包含.(点),如:"java","txt")作为key, 用个数作为value,放入到map集
-
5.键盘录入一个文件夹路径,统计该文件夹(包含子文件夹)中每种类型的文件及个数,注意:用文件类型(后缀名,不包含.(点),如:"java","txt")作为key,
-
键盘录入一个文件夹路径,统计该文件夹(包含子文件夹)中每种类型的文件及个数,注意:用文件类型(后缀名,不包含.(点),如:"java","txt")作为key
-
二叉树找最近祖先节点和到某一节点的路径
-
C题解:有一棵树,一开始每个点有一个初始值,每一个点的新数为它到树顶的路径中的所有数,去掉一个数后的最大公因数中的最大值
-
daklqw 的 T3(点分树上数据结构优化DP)
-
分治 平面上的最近点对