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
5 41 2 31 3 11 4 23 5 10 0
Sample Output
8 题目大意：有一颗由n个点组成的树，问树上两点间距离小于等于k的点对有多少对 输入：多组数据输入。每组数据第1行n，k，接下来n-1行，u，v，l表示点u与点v之间有一条长为l的边 输出：点对个数 基本算法：点分治 点分治，本质还是分治算法 对于一棵树，简单的递归搜索的复杂度，呵呵~~， 所以为了降低复杂度，通俗点儿说就是将一棵树拆开 一棵树的复杂度之所以高，是因为它有可能很深， 所以拆要使拆开后的几棵树最深的最小 那么选取的这个点就是树的重心 树的重心通俗点儿说就是删除重心后最大的连通块最小 找出重心后，树上的点的路径就可以分为 经过重心的 和 不过重心的 对于经过重心的， 1、统计出过重心的所有点的满足条件的数目=ans1 2、对于每棵子树，统计一遍自己内部满足条件的数目=ans2 ans=ans1-所有的ans2 对于不经过重心的，继续递归 本人点分治理解不深，对点分治更详细的解读 推荐博客:对于文章中出现的错误，欢迎各位指正
代码中数组含义：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]
#include#include #include #define N 10010#define inf 20001using 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]
加的是无向边，链表忘了开双倍，RE。。。。。。
#include#include #include #define inf 0x7fffffffusing 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]