Loading...

POJ 1741 Tree

check评论:0 条 remove_red_eye浏览量:394 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-09

蒟蒻的我刚学点分治,就来刷道模板

给定一棵$n$个点的树,求出树中距离小于等于$k$的点对

一看就是点分治啊qwq

我们每次求出一棵子树的重心,然后找出所有点距离之后二分就行了qwq

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;
int head[10010],n,dep[10010],vis[10010];
int rt,sum,siz[10010],f[10010],o[10010];
int k;
int cnt=0,ans;
struct edge
{
    int next,to,dis;
}e[20010];
void getrt(int u,int fa)
{
    siz[u]=1;
    f[u]=0;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa||vis[v])
        {
            continue;
        }
        getrt(v,u);
        siz[u]+=siz[v];
        f[u]=max(f[u],siz[v]); 
    }
    f[u]=max(f[u],sum-siz[u]);
    if(f[u]<f[rt])
    {
        rt=u;
    }
}
void getdis(int u,int fa)
{
    o[++o[0]]=dep[u];
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa||vis[v])
        {
            continue;
        }
        dep[v]=dep[u]+e[i].dis;
        getdis(v,u);
    }
}
int calc(int u,int dp)
{
    o[0]=0;
    dep[u]=dp;
    getdis(u,0);
    sort(o+1,o+o[0]+1);
    int l=1,r=o[0],ans=0;
    while(l<r)
    {
        if(o[l]+o[r]<=k)
        {
            ans+=r-l;
            l++;
        }
        else
        {
            r--;
        }
    }
    return ans;
}
void solve(int u)
{
    ans+=calc(u,0);
    vis[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(vis[v])
        {
            continue;
        }
        ans-=calc(v,e[i].dis);
        rt=0;
        sum=siz[v];
        getrt(v,0);
        solve(rt);
    }
}
int main()
{
    while(1)
    {
        cin>>n>>k;
        if(!n)
        {
            return 0;
        }
        memset(e,0,sizeof(e));
        memset(head,0,sizeof(head));
        memset(o,0,sizeof(o));
        memset(dep,0,sizeof(dep));
        memset(vis,0,sizeof(vis));
        cnt=0;
        ans=0;
        for(int i=1;i<n;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            e[++cnt]=(edge){head[x],y,z};
            head[x]=cnt;
            e[++cnt]=(edge){head[y],x,z};
            head[y]=cnt;
        }
        rt=0;
        sum=f[rt]=n;
        getrt(1,0);
        solve(rt);
        cout<<ans<<endl;
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名