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 to, w, next;
 11 }edge[maxn*2];
 12 int head[maxn], vis[maxn], size[maxn], mu[maxn];
 13 int tot, n, k, ans, root, mini, d, dis[maxn];
 14
 15 void init ()
 16 {
 17     tot = ans = 0;
 18     memset (head, -1, sizeof(head));
 19     memset (vis, 0, sizeof(vis));
 20 }
 21 void Add (int from, int to, int val)
 22 {
 23     edge[tot].to = to;
 24     edge[tot].w = val;
 25     edge[tot].next = head[from];
 26     head[from] = tot ++;
 27 }
 28 void dfsroot (int u, int father)
 29 {
 30     size[u] = 1;
 31     mu[u] = 0;
 32     for (int i=head[u]; i!=-1; i=edge[i].next)
 33     {
 34         int v = edge[i].to;
 35         if (!vis[v] && v!=father)
 36         {
 37             dfsroot (v, u);
 38             size[u] += size[v];
 39             mu[u] = max(mu[u], size[v]);
 40         }
 41     }
 42     mu[u] = max (mu[u], n-size[u]);
 43     if (mini > mu[u])
 44         root = u;
 45 }
 46 void dfsdist (int u, int father, int w)
 47 {
 48     dis[d ++] = w;
 49     for (int i=head[u]; i!=-1; i=edge[i].next)
 50     {
 51         int v = edge[i].to;
 52         if (!vis[v] && v!=father)
 53             dfsdist (v, u, w+edge[i].w);
 54     }
 55 }
 56 int calc (int u, int w)
 57 {
 58     int res = 0;
 59     d = 0;
 60     dfsdist (u, 0, w);
 61     sort (dis, dis+d);
 62     int i=0, j=d-1;
 63     while (i < j)
 64     {
 65         while (dis[i] + dis[j] > k && i<j)
 66             j --;
 67         res += j - i;
 68         i ++;
 69     }
 70     return res;
 71 }
 72 void dfs (int u)
 73 {
 74     mini = n;
 75     dfsroot (u, 0);
 76     ans += calc (root, 0);
 77     vis[root] = 1;
 78     for (int i=head[root]; i!=-1; i=edge[i].next)
 79     {
 80         int v = edge[i].to;
 81         if (!vis[v])
 82         {
 83             ans -= calc (v, edge[i].w);
 84             dfs (v);
 85         }
 86     }
 87 }
 88 int main ()
 89 {
 90     while (scanf ("%d %d", &n, &k), n+k)
 91     {
 92         init ();
 93         for (int i=1; i<n; i++)
 94         {
 95             int u, v, w;
 96             scanf ("%d %d %d", &u, &v, &w);
 97             Add (u, v, w);
 98             Add (v, u, w);
 99         }
100         dfs (1);
101         printf ("%d\n", ans);
102     }
103     return 0;
104 }
时间: 07-26

Poj 1741 Tree (树的分治)的相关文章

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 in

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 ——(树分治)

思路参考于: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>

数据结构(树,点分治):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 e

POJ 1741 Tree (树的分治,树的重心)

题意:给一棵树,n个节点,给定一个数k,求任意满足dist(a,b)<=k的点对的数量. 思路: 这道题的思路比较简单,但是细节很多. 此题可以用分治法,如何分治? (1)如果path(a,b)不经过根,那么肯定在根的某棵子树下,递归解决. (2)如果path(a,b)经过根,那么肯定在根的不同子树下,处理它. 怎样处理?如果知道了每棵子树中的节点到根的距离,暂且将每棵子树的节点分到每个独立的桶里.每个节点都可以和其他桶里的点组成点对,只要距离<=k的话就满足要求了.逐个算可能超时了,用个简单

POJ 1741 Tree(树分治|ltc男人八题)

 题意:求树上距离小于等于K的点对有多少个. 思路:这道题很容易想到树分治,对于当前的根节点来说,任意两个结点之间要么过根结点,要么在一棵子树中. 那么我们dfs一次求出所有点到根结点的距离,然后用o(n)的时间判定有多少节点对符合,(判断方法稍后说) 但是这样有很多在一颗子树中的节点对我们会求重复,我们需要减去在一棵子树中结点对小于等于k的数量,也就是说,我们这一步求的是在不同子树中距离小于等于k的节点对的个数. 接下来说判定方法,将每个点到根结点的距离排序,用两个指针指向队首和队尾,当结

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