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>
  4 #include <vector>
  5 using namespace std;
  6 const int N = 10000 + 5;
  7
  8 struct edge
  9 {
 10     int v,w;
 11 };
 12 int n,k,root,sz,ans;
 13 bool vis[N];
 14 int son[N],f[N],d[N];
 15 vector<edge> G[N];
 16 vector<int> dep;
 17 void init()
 18 {
 19     memset(vis,false,sizeof(vis));
 20     for(int i=1;i<=n;i++) G[i].clear();
 21     memset(son,0,sizeof son);
 22     memset(f,0,sizeof f);
 23 }
 24 void  addEdge(int u,int v,int w)
 25 {
 26     G[u].push_back((edge){v,w});
 27     G[v].push_back((edge){u,w});
 28 }
 29 void getRoot(int u,int fa)
 30 {
 31     son[u] = 1; f[u] = 0;
 32     for(int i=0;i<G[u].size();i++)
 33     {
 34         edge e = G[u][i];
 35         int v = e.v;
 36         if(v == fa || vis[v]) continue;
 37         getRoot(v,u);
 38         son[u] += son[v];
 39         f[u] = max(f[u], son[v]);
 40     }
 41     f[u] = max(f[u], sz-son[u]);
 42     if(f[u] < f[root]) root = u;
 43 }
 44 void getDep(int u,int fa)
 45 {
 46     dep.push_back(d[u]);
 47     for(int i=0;i<G[u].size();i++)
 48     {
 49         edge e = G[u][i];
 50         int v = e.v, w= e.w;
 51         if(v == fa || vis[v]) continue;
 52         d[v] = d[u] + w;
 53         getDep(v,u);
 54     }
 55 }
 56 int cal(int u,int len)
 57 {
 58     dep.clear(); d[u] = len;
 59     getDep(u, 0);
 60     sort(dep.begin(), dep.end());
 61     int ret = 0;
 62     for(int l=0,r=dep.size()-1;l<r;)
 63     {
 64         if(dep[l] + dep[r] <= k) ret += r - (l++);
 65         else r--;
 66     }
 67     return ret;
 68 }
 69 void solve(int u)
 70 {
 71     ans += cal(u, 0);
 72     vis[u] = 1;
 73     for(int i=0;i<G[u].size();i++)
 74     {
 75         edge e = G[u][i];
 76         int v = e.v, w = e.w;
 77         if(vis[v]) continue;
 78         ans -= cal(v, w);
 79         f[0] = sz = son[v];
 80         getRoot(v, root=0);
 81         solve(root);
 82     }
 83 }
 84
 85 int main()
 86 {
 87     while(scanf("%d%d",&n,&k) == 2)
 88     {
 89         if(n == 0 && k == 0) break;
 90         init();
 91         for(int i=1;i<=n-1;i++)
 92         {
 93             int u,v,w;
 94             scanf("%d%d%d",&u,&v,&w);
 95             addEdge(u,v,w);
 96         }
 97         f[0] = sz = n;
 98         getRoot(1,root=0);
 99         ans = 0;
100         solve(root);
101         printf("%d\n",ans);
102     }
103     return 0;
104 }
时间: 01-28

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

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

题目链接: 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 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

POJ 1741 Tree ——点分治

[题目分析] 这貌似是做过第三道以Tree命名的题目了. 听说树分治的代码都很长,一直吓得不敢写,有生之年终于切掉这题. 点分治模板题目.自己YY了好久才写出来. 然后1A了,开心o(* ̄▽ ̄*)ブ [代码] #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define maxn 20005 #define inf 0x3f3f3f3f using

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 点分治

题意 给定 n 个节点的树. 求有多少对节点 (u, v) , 满足 dist(u, v) <= K . n <= 10000. 实现 #include <cstdio> #include <cstring> #include <cstdlib> #include <cctype> #include <algorithm> #include <vector> using namespace std; #define F(i

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

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

【BZOJ-1468】Tree 树分治

1468: Tree Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 1025  Solved: 534[Submit][Status][Discuss] Description 给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K Input N(n<=40000) 接下来n-1行边描述管道,按照题目中写的输入 接下来是k Output 一行,有多少对点之间的距离小于等于k Sample Input 7 1 6 13 6