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

POJ 1741 Tree - 点分治+容斥

程序员文章站 2022-05-08 19:01:43
...
考察内容:树分治+容斥


题意:给定一棵树,求两个节点的距离不大于m的种类的数目


分析:
1.计算一棵树的重心: 重心即为最大子树规模最小的点,可以维护min值找到重心,有一种更简单的方法,即对于一棵数量为tot的树,其重心一定满足最大子树不大于tot/2,证明方法为反证法,此节点在子树中必不存在一个最大子树小于tot/2的点。
2.分治一棵子树中所有的距离,进行容斥,标记,然后继续递归子树(细节见代码)


注意:get到了memset可以清空部分,可以加快速度


//点分治模板 
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>

using namespace std;

const int maxn=20005;

struct line
{
    int to,next,val;
}l[maxn];
int cntl;
int n,m;
int head[maxn];
int sz[maxn];
int mxsz[maxn];
bool vst[maxn]; 

int a[maxn],cnt;

void insert(int a,int b,int c)
{
    l[++cntl].to=b;l[cntl].val=c;l[cntl].next=head[a];head[a]=cntl;
}
void dfs_getsz(int x,int fa)
{
    sz[x]=1;mxsz[x]=0;
    for(int i=head[x];i;i=l[i].next)
        if(!vst[l[i].to]&&fa!=l[i].to)
    {
        dfs_getsz(l[i].to,x);
        sz[x]+=sz[l[i].to];
        mxsz[x]=max(mxsz[x],sz[l[i].to]);
    }
}
void dfs_geto(int x,int fa,int tot,int &o)
{
    mxsz[x]=max(mxsz[x],tot-sz[x]);
    if(mxsz[x]<=tot/2)o=x;
    for(int i=head[x];i;i=l[i].next)
        if(!vst[l[i].to]&&fa!=l[i].to)//vst:被讨论过partition的点不用再统计 
            dfs_geto(l[i].to,x,tot,o);
}
int geto(int x)
{
    int o;
    dfs_getsz(x,-1);
    dfs_geto(x,-1,sz[x],o);
    return o;
}
void dfs_getdist(int x,int fa,int val)
{
    a[++cnt]=val;
    for(int i=head[x];i;i=l[i].next)
        if(!vst[l[i].to]&&fa!=l[i].to)
            dfs_getdist(l[i].to,x,val+l[i].val);
}
int partition(int x)
{
    x=geto(x);
    vst[x]=true;
    cnt=0; 
    a[++cnt]=0;//其重心到自身也有一个0的路径 
    int ans=-1;//减去0 0此种情况
    for(int i=head[x];i;i=l[i].next)
        if(!vst[l[i].to])
    {
        int cur=cnt;//统计经过子节点的各种距离的头指针 
        dfs_getdist(l[i].to,x,l[i].val);//计算各种长度 ,改变c 
        sort(a+cur+1,a+cnt+1);//cnt经过更新成为尾指针 
        int point=cnt;
        for(int j=cur+1;j<=cnt;j++)
        {//将所有距离都排序粘贴到两侧,然后比对,当大于m时移动指针(双指针法) 
            while(a[point]+a[j]>m&&point>cur)point--;
            ans-=point-cur;//容斥掉在子树中的dist+dist<m情况 
        }
    }
    sort(a+1,a+cnt+1);
    int point=cnt;
    for(int i=1;i<=cnt;i++)
    {
        while(point&&a[point]+a[i]>m)point--;
        ans+=point;//加上所有<m的情况 
    }
    for(int i=head[x];i;i=l[i].next)
        if(!vst[l[i].to])
            ans+=partition(l[i].to);
    return ans;
}
int main()
{
    while(~scanf("%d%d",&n,&m)&&(n||m))
    {
        cntl=0;
        memset(head+1,0,sizeof(int)*n);
        memset(vst+1,0,sizeof(int)*n);
        memset(sz+1,0,sizeof(int)*n);
        memset(mxsz+1,0,sizeof(int)*n);
        for(int i=1;i<n;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            insert(a,b,c);
            insert(b,a,c);
        }
        printf("%d\n",partition(1)/2);//边重复计算了两遍,所以除掉2 
    } 
    return 0;
}