POJ 1741 Tree 求树上路径小于k的点对个数)

POJ 1741 Tree

Description

Give a tree with n vertices,each edge has a length(positive integer less than 1001).
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.

Input

The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l.
The last test case is followed by two zeros.

Output

For each test case output the answer on a single line.

Sample Input

Sample Output

8
题目大意：有一颗由n个点组成的树，问树上两点间距离小于等于k的点对有多少对
输入：多组数据输入。每组数据第1行n，k，接下来n-1行，u，v，l表示点u与点v之间有一条长为l的边
输出：点对个数
基本算法：点分治
点分治，本质还是分治算法
对于一棵树，简单的递归搜索的复杂度，呵呵~~，
所以为了降低复杂度，通俗点儿说就是将一棵树拆开
一棵树的复杂度之所以高，是因为它有可能很深，
所以拆要使拆开后的几棵树最深的最小
那么选取的这个点就是树的重心 
树的重心通俗点儿说就是删除重心后最大的连通块最小
找出重心后，树上的点的路径就可以分为
经过重心的 和 不过重心的
对于经过重心的，
1、统计出过重心的所有点的满足条件的数目=ans1
2、对于每棵子树，统计一遍自己内部满足条件的数目=ans2
ans=ans1-所有的ans2
对于不经过重心的，继续递归
本人点分治理解不深，对点分治更详细的解读 推荐博客:http://www.cnblogs.com/chty/p/5912360.html
对于文章中出现的错误，欢迎各位指正

代码中数组含义：head[],链表  son[i]=j，以i为根的所有子树总共有j个节点（包括i）    
　　　　　f[i]=j以i为根的所有子树中，最大的一颗子树有j个节点（不包括i）
        sum，当前计算的树或子树的点的个数      
　　　　　d[i]=j，点i到当前所选的根节点距离为j deep[]，d数组的汇总
代码中函数作用：getroot，找重心 getdeep，统计点之间的距离 cal，统计满足条件的点对数目
部分代码细节：
getroot函数:son[x]=1,因为son包含自己 f[x]=0，因为f可能存有上一次的结果
f[x]=max(f[x],sum-son[x]);①解释了为什么son包含自己，sum是总点数，son[x]是除临时指定的父节点所在子树的子树节点总数，相减就是临时父节点所在子树节点总数
因为父节点是临时指定的，所以也有可能成为x的孩子节点，所以父节点所在子树也作为x的一颗子树 ②在>2个点时，保证不让叶子节点成为重心
work函数：root=0 && main函数 f[0]=inf 这两个互相照应，删除选定的根之后，让根=0，因为f[0]=inf,这样在getroot函数里才保证了f[x]<f[root]，更新root

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 10010
#define inf 20001
using namespace std;
int n,k,cnt,head[N],son[N],f[N],sum,ans,root,d[N],deep[N];
bool vis[N];
struct node
{
int next,to,w;
}e[2*N];
inline void add(int u,int v,int w)
{
    e[++cnt].to=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;
    e[++cnt].to=u;e[cnt].w=w;e[cnt].next=head[v];head[v]=cnt;
}
inline void pre()
{
    memset(head,0,sizeof(head));
    memset(vis,false,sizeof(vis));
    ans=0;cnt=0;root=0;
}
inline void getroot(int x,int fa)
{
    son[x]=1;f[x]=0;
for(int i=head[x];i;i=e[i].next)
    {
if(e[i].to==fa||vis[e[i].to]) continue;
        getroot(e[i].to,x);
        son[x]+=son[e[i].to];
        f[x]=max(f[x],son[e[i].to]);
    }
    f[x]=max(f[x],sum-son[x]);
if(f[x]<f[root]) root=x;
}
inline void getdeep(int x,int fa)
{
    deep[++deep[0]]=d[x];
for(int i=head[x];i;i=e[i].next)
    {
if(e[i].to==fa||vis[e[i].to]) continue;
        d[e[i].to]=d[x]+e[i].w;
        getdeep(e[i].to,x);
    }
}
inline int cal(int x,int p)
{
    d[x]=p;deep[0]=0;
    getdeep(x,0);
    sort(deep+1,deep+deep[0]+1);
int t=0,l,r;
for(l=1,r=deep[0];l<r;)
    {
if(deep[l]+deep[r]<=k) {t+=r-l;l++;}
else r--;
    } 
return t;
}
inline void work(int x)
{
    ans+=cal(x,0);
    vis[x]=true;
for(int i=head[x];i;i=e[i].next)
    {
if(vis[e[i].to]) continue;
        ans-=cal(e[i].to,e[i].w);
        sum=son[e[i].to];
        root=0;
        getroot(e[i].to,0);
        work(root);
    }
}
int main()
{
while(1)
    {
        scanf("%d%d",&n,&k);
if(!n) return 0;
        pre();
int u,v,w;
for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);        
        }
        sum=n;f[0]=inf;
        getroot(1,0); 
        work(root);
        printf("%d\n",ans);
    }
}

加的是无向边，链表忘了开双倍，RE。。。。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
int n,K,cnt,sum,ans,root;
int head[10005],deep[10005],d[10005],f[10005],son[10005];
bool vis[10005];
struct data{int to,next,v;}e[20005];
inline int read()
{
int x=0;char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
return x;
}
inline void insert(int u,int v,int w)
{
    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;
    e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;e[cnt].v=w;
}
//最小递归层数    why联通的节点数量最小? 不是层数？ 
inline void getroot(int x,int fa)
{
    son[x]=1;f[x]=0;//son：以x为根的子树的节点个数，包括自己 
//f[x]=0 不能删  因为f[x]可能存有上一次的结果 
for(int i=head[x];i;i=e[i].next)
    {
if(e[i].to==fa||vis[e[i].to]) continue;  //vis=true表示节点已删除 
        getroot(e[i].to,x);
        son[x]+=son[e[i].to];
        f[x]=max(f[x],son[e[i].to]);
    }
    f[x]=max(f[x],sum-son[x]);
//树本有根，点分治重新找根，所以以x为根的子树除了已递归到的，还有以父节点为根的子树，这也是son[x]=1的原因 
if(f[x]<f[root]) root=x;//找到的根满足它的最大子树最小 
}
inline void getdeep(int x,int fa)
{
    deep[++deep[0]]=d[x];//deep[0]总的节点数，deep 每个点到根节点的距离 
for(int i=head[x];i;i=e[i].next)
    {
if(e[i].to==fa||vis[e[i].to]) continue;
        d[e[i].to]=d[x]+e[i].v;
        getdeep(e[i].to,x);
    }
}
inline int cal(int x,int now)//now初始为0 
{
    d[x]=now;deep[0]=0;//d是长度 
    getdeep(x,0);//得到以x为根的子树中，每个点到x的距离 
    sort(deep+1,deep+deep[0]+1);
int t=0,l,r;
for(l=1,r=deep[0];l<r;)
    {
if(deep[l]+deep[r]<=K) {t+=r-l;l++;}
else r--;
    }
return t;
}
inline void work(int x)//x是确定的根 
{
    ans+=cal(x,0);
    vis[x]=1;
for(int i=head[x];i;i=e[i].next)
    {
if(vis[e[i].to]) continue;
        ans-=cal(e[i].to,e[i].v);
        sum=son[e[i].to];
        root=0;//删除原根节点后，重新找根节点，f【0】=inf 
        getroot(e[i].to,root);
        work(root);
    }
}
int main()
{
while(1)
    {
        ans=0,root=0,cnt=0;
        memset(vis,0,sizeof(vis));
        memset(head,0,sizeof(head));
        n=read();K=read();
if(!n) return 0;
for(int i=1;i<n;i++)
        {
int u=read(),v=read(),w=read();
            insert(u,v,w);
        }
        sum=n;f[0]=inf;//sum:用sum-节点已统计的子树节点个数=以节点临时父节点为根的子树节点个数 
//f  记录以x为根的最大的子树的大小，最后从f中取最小值   
//f[0]=inf 不能删  因为每次getroot 更新root根据f[x]是否小于f[root]，每次删除一个点root=0 
        getroot(1,0);//找第一个根 ，临时从第1个点开始找 
        work(root);
        printf("%d\n",ans);
    }
}

学习时打的注释

秒客网

POJ 1741 Tree 求树上路径小于k的点对个数)

相关文章