POJ 1741 Tree - 点分治+容斥
程序员文章站
2022-05-08 19:01:43
...
考察内容:树分治+容斥
题意:给定一棵树,求两个节点的距离不大于m的种类的数目
分析:
1.计算一棵树的重心: 重心即为最大子树规模最小的点,可以维护min值找到重心,有一种更简单的方法,即对于一棵数量为tot的树,其重心一定满足最大子树不大于tot/2,证明方法为反证法,此节点在子树中必不存在一个最大子树小于tot/2的点。
2.分治一棵子树中所有的距离,进行容斥,标记,然后继续递归子树(细节见代码)
题意:给定一棵树,求两个节点的距离不大于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;
}