首页 > 其他 > 详细

【BZOJ】1468: Tree(POJ1741)

时间:2018-01-20 12:24:43      阅读:212      评论:0      收藏:0      [点我收藏+]

【题意】给定带边权树,求两点距离<=k的点对数。n<=40000。

【算法】点分治

【题解】对于一个区域,选择其重心x作为根,则划分出来的每棵子树都是子区域,可以证明至多划分log n次(通过vis[]划分区域)。每次划分所有点都扫描一次,所以仅遍历的复杂度是O(n log n)。

对于本题,将点x的所有子树节点dis处理出来后排序,然后用双指针法易得<=k的点对数。

但是,这样会把来自同一子树的路径也计算进去,需要减去。来自同一子树y的距离<=k的路径的数量等同于子树y内路径的距离+2*w<=k的路径的数量。

 所以,设dis[y]=w后再减去子树y的路径数即可。

 具体做法:calc(x,0)表示dis[x]=0统计得到的子树x内<=k的路径数,则ans(x)=calc(x,0)-calc(y,w),y=son[x],w是边(x,y)的权值。

技术分享图片
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=50010;
ll ans;
int root,first[maxn],tot,cnt,sz[maxn],sum,d[maxn],k,n;
bool vis[maxn];
struct edge{int v,w,from;}e[maxn*2];
void insert(int u,int v,int w){tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;}
void getroot(int x,int fa){
    sz[x]=1;
    bool ok=1;
    for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa&&!vis[e[i].v]){
        getroot(e[i].v,x);
        sz[x]+=sz[e[i].v];
        if(sz[e[i].v]>sum/2)ok=0;
    }
    if(sum-sz[x]<=sum/2&&ok)root=x;
}
void getdeep(int x,int fa,int w){
    d[++cnt]=w;
    for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa&&!vis[e[i].v])getdeep(e[i].v,x,w+e[i].w);
}
ll calc(int x,int w){
    cnt=0;getdeep(x,0,w);
    sort(d+1,d+cnt+1);
    int l=1,r=cnt;
    ll sum=0;
    while(l<r){
        if(d[l]+d[r]<=k){sum+=r-l;l++;}
        else r--;
    }
    return sum;
}
void solve(int x,int s){
    ans+=calc(x,0);vis[x]=1;
    for(int i=first[x];i;i=e[i].from)if(!vis[e[i].v]){
        ans-=calc(e[i].v,e[i].w);
        if(sz[e[i].v]>sz[x])sum=s-sz[x];else sum=sz[e[i].v];
        getroot(e[i].v,x);
        solve(root,sum);
    }
}
int main(){
    scanf("%d",&n);
    int u,v,w;
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&u,&v,&w);
        insert(u,v,w);insert(v,u,w);
    }
    scanf("%d",&k);
    sum=n;
    getroot(1,0);
    ans=0;
    solve(root,n);
    printf("%lld\n",ans);
    return 0;
}
View Code

 

【BZOJ】1468: Tree(POJ1741)

原文:https://www.cnblogs.com/onioncyc/p/7067414.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!