POJ 1741 Tree(树的点分治,入门题)

Tree

Time Limit: 1000MS   Memory Limit: 30000K
Total Submissions: 21357   Accepted: 7006

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 4
1 2 3
1 3 1
1 4 2
3 5 1
0 0

Sample Output

8

Source

[email protected]

题目链接:http://poj.org/problem?id=1741

题目大意:

给定一棵N个节点、边上带权的树,再给出一个K,询问有多少个数对(i,j)满足i<j,且i与j两点在树上的距离小于等于K。

数据规模:

多组测试数据,每组数据满足N≤10000,1≤边上权值≤1000,1≤K≤10^9。

出处:

楼天城男人必做8题之一……

思路:

最容易想到的算法是:从每个点出发遍历整棵树,统计数对个数。

由于时间复杂度O(N^2),明显是无法满足要求的。

对于一棵有根树, 树中满足要求的一个数对所对应的一条路径,必然是以下两种情况之一:

1、经过根节点

2、不经过根节点,也就是说在根节点的一棵子树中

对于情况2,可以递归求解,下面主要来考虑情况1。

设点i的深度为Depth[i],父亲为Parent[i]。

若i为根,则Belong[i]=-1,若Parent[i]为根,则Belong[i]=i,否则Belong[i]=Belong[Parent[i]]。

这三个量都可以通过一次BFS求得。

我们的目标是要统计:有多少对(i,j)满足i<j,Depth[i]+Depth[j]<=K且Belong[i]<>Belong[j]

如果这样考虑问题会变得比较麻烦,我们可以考虑换一种角度:

设X为满足i<j且Depth[i]+Depth[j]<=K的数对(i,j)的个数

设Y为满足i<j,Depth[i]+Depth[j]<=K且Belong[i]=Belong[j]数对(i,j)的个数

那么我们要统计的量便等于X-Y

求X、Y的过程均可以转化为以下问题:

已知A[1],A[2],...A[m],求满足i<j且A[i]+A[j]<=K的数对(i,j)的个数

对于这个问题,我们先将A从小到大排序。

设B[i]表示满足A[i]+A[p]<=K的最大的p(若不存在则为0)。我们的任务便转化为求出A所对应的B数组。那么,若B[i]>i,那么i对答案的贡献为B[i]-i。

显然,随着i的增大,B[i]的值是不会增大的。利用这个性质,我们可以在线性的时间内求出B数组,从而得到答案。

综上,设递归最大层数为L,因为每一层的时间复杂度均为“瓶颈”——排序的时间复杂度O(NlogN),所以总的时间复杂度为O(L*NlogN)

然而,如果遇到极端情况——这棵树是一根链,那么随意分割势必会导致层数达到O(N)级别,对于N=10000的数据是无法承受的。因此,我们在每一棵子树中选择“最优”的点分割。所谓“最优”,是指删除这个点后最大的子树尽量小。这个点可以通过树形DP在O(N)时间内求出,不会增加时间复杂度。这样一来,即使是遇到一根链的情况时,L的值也仅仅是O(logN)的。

因此,改进后算法时间复杂度为O(Nlog^2N),可以AC。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <vector>
 6 #include <algorithm>
 7 using namespace std;
 8 const int N = 1e5+20, M = 1e2+10, mod = 1e9+7, inf = 1e9+1000;
 9 typedef long long ll;
10
11 int n,m,root,t,ans,allnode,siz[N],K,head[N],vis[N],d[N];
12 int deep[N];//路径长度//deep[0]子节点个数
13 int f[N];//重心
14
15 struct edg{int to,next,v;}e[N * 4];//前向星存边
16 void add(int u,int v,int w) {e[t].to=v;e[t].next=head[u];e[t].v=w;head[u]=t++;}//加边
17
18 //获取重心
19 void getroot(int x,int fa) {
20     siz[x] = 1;
21     f[x] = 0;
22     for(int i=head[x];i;i=e[i].next) {
23         int to = e[i].to;
24         if(to == fa || vis[to]) continue;
25         getroot(to,x);
26         siz[x] += siz[to];
27         f[x] = max(f[x] , siz[to]);
28     }
29     f[x] = max(allnode-siz[x] , f[x]);
30     if(f[x] < f[root]) root = x;
31 }
32
33 void getdeep(int x,int fa) {//获取子树所有节点与根的距离
34     deep[++deep[0]] = d[x];
35     for(int i=head[x];i;i=e[i].next) {
36         int to = e[i].to;
37         if(to == fa || vis[to]) continue;
38         d[to] = d[x] + e[i].v;
39         getdeep(to,x);
40     }
41 }
42 int cal(int x,int now) {//计算当前以重心x的子树下,所有情况的答案
43     d[x]=now;deep[0]=0;
44     getdeep(x,0);
45     sort(deep+1,deep+deep[0]+1);
46     int all = 0;
47     for(int l=1,r=deep[0];l<r;) {
48         if(deep[l]+deep[r] <= K) {all += r-l;l++;}
49         else r--;
50     }
51     return all;
52 }
53
54 void work(int x) {//以x为重心进行计算
55     vis[x] = 1;
56     ans+=cal(x,0);
57     for(int i=head[x];i;i=e[i].next) {
58         int to = e[i].to;
59         if(vis[to]) continue;
60         ans -= cal(to,e[i].v);
61         allnode = siz[to];
62         root=0;
63         getroot(to,x);
64         work(root);
65     }
66 }
67
68 int main()
69 {
70     while(~scanf("%d%d",&n,&K)) {
71         if(!n&&!m) break;
72         memset(head,0,sizeof(head));
73         memset(vis,0,sizeof(vis));
74         t = 1;
75         for(int i=1;i<n;i++) {
76             int a,b,c;
77             scanf("%d%d%d",&a,&b,&c);
78             add(a,b,c) , add(b,a,c);
79         }
80         root=ans=0;
81         allnode=n;f[0]=inf;
82         getroot(1,0);
83         work(root);
84         printf("%d\n",ans);
85     }
86 }

时间: 03-24

POJ 1741 Tree(树的点分治,入门题)的相关文章

Poj 1741 Tree (树的分治)

题目链接: Poj 1741 Tree 这个题目Tle的好苦啊,原来一直是树的重心没找对,Tle好长时间,终于对了,好感动,先贴个代码. 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 10010; 8 struct node 9 { 10 int

POJ 1741 Tree 树分治(点分治)

题意:给你一颗带边权树,问你其中 dis(v,u) <= k 的对数 解题思路: 首先推荐大家看 09年国家集训队漆子超 的论文 看到这题  我们可以有三种思路 第一种是枚举起点,遍历整颗树找对数    时间复杂度 为  O(n^2),空间复杂度为 O(n) 第二种是树形dp的思想     每个节点用 长度为 K 数组维护 ,递归求解  时间复杂度为 O(n ^k)空间复杂度 为 O(n) 第三种就是我们要用到的点分治的思想. 这种思想的具体思路是  先找到一个  根  对这个根进行 深搜, 找

POJ 1741 Tree(树分治)

去网上搜题解大多数都是说论文,搜了论文看了看,写的确实挺好,直接复制过来. 不过代码中有些细节还是要注意的,参考这篇http://blog.sina.com.cn/s/blog_6d5aa19a0100o73m.html一段 设X为满足i<j且Depth[i]+Depth[j]<=K的数对(i,j)的个数设Y为满足i<j,Depth[i]+Depth[j]<=K且Belong[i]=Belong[j]数对(i,j)的个数那么我们要统计的量便等于X-Y 求X.Y的过程均可以转化为以下

POJ 1741 Tree 树形DP(分治)

链接:id=1741">http://poj.org/problem?id=1741 题意:给出一棵树,节点数为N(N<=10000),给出N-1条边的两点和权值,给出数值k,问树上两点最短距离小于k的点对有多少个. 思路:拿到题的第一反应是LCA问题,只是细一想询问次数极限情况能够达到10000*5000次.即使用Tarjan也是超时没商议的. 2009年国家队论文提供了树的分治思想,对于本题就是树的分治的点分治的应用.每次找到能使含节点最多的子树的节点最少的根分而治之,相同方式分

【POJ 1741】 Tree (树的点分治)

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)

poj 1744 tree 树分治

Tree Time Limit: 1000MS   Memory Limit: 30000K       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 ve

poj1741+poj1987+poj2114——点分治入门题集合

最近看了看点分治,从poj上找到几道题,都比较裸.而且感觉这三道题都长得差不多呀qwq ------------------------------------------------ [poj 1741]Tree 题意:给定一棵边带权的树,求两点之间的距离小于或等于K的点对个数. 找重心,相当于把无根树转变为有根树.再利用分治的思想(根据经过重心或不经过重心来划分). 对于在同一个子树的情况要单独拎出来算并减去它们(因为是不该算在内的呀qwq) 另外选取重心的好处是时间复杂度O(NlogN*l

COGS 577 蝗灾 [CDQ分治入门题]

题目链接 昨天mhr神犇,讲分治时的CDQ分治的入门题. 题意: 你又一个w*w正方形的田地. 初始时没有蝗虫. 给你两个操作: 1. 1 x y z: (x,y)这个位置多了z只蝗虫. 2. 2 x1 y1 x2 y2: 询问(x1,y1)到(x2,y2)这个矩形内的蝗虫数量. 其中 W<=500000,操作数<=200000 . 题解: w范围太大,无法使用二维数据结构. 于是我们可以分治操作. CDQ分治:定义 solve(l,r) 设m=(l+r)/2; 先计算 l-m 修改操作对 m

POJ 1741 Tree ——(树分治)

思路参考于:http://blog.csdn.net/yang_7_46/article/details/9966455,不再赘述. 复杂度:找树的重心然后分治复杂度为logn,每次对距离数组dep排序复杂度为nlogn,而找重心的复杂度为dfs的复杂度--O(n),因此总的复杂度为O(nlognlogn). 因为第一次写树分治,留个代码: 1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h>