欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[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);
}