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



题意:求树上距离小于等于K的点对有多少个。

思路:这道题很容易想到树分治,对于当前的根节点来说,任意两个结点之间要么过根结点,要么在一棵子树中。

那么我们dfs一次求出所有点到根结点的距离,然后用o(n)的时间判定有多少节点对符合,(判断方法稍后说)

但是这样有很多在一颗子树中的节点对我们会求重复,我们需要减去在一棵子树中结点对小于等于k的数量,也就是说,我们这一步求的是在不同子树中距离小于等于k的节点对的个数。

接下来说判定方法,将每个点到根结点的距离排序,用两个指针指向队首和队尾,当结点距离和大于k时,队尾指针减一

否则更新答案并将队首指针加一。

这道题还有一个问题样例相当好,因为假如树退化成一条链时,如果我们以任意结点为根那么递归深度将达到O(n),将会tle

所以每次树分治时我们都要找到当前树的重心,并以重心为根继续分治。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#define eps 1e-6
#define LL long long
#define pii (pair<int, int>)
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;  

const int maxn = 10000 + 100;
const int INF = 0x3f3f3f3f;

int n, root, k, cnt; //root记录重心
int des[maxn], bal[maxn], vis[maxn];//des记录以该节点为祖先的后代数,bal记录以该节点为根的最大子树的节点数
vector<int> G[maxn], L[maxn], dist; 

void get_root(int cur, int fa) {
	des[cur] = 1;
	bal[cur] = 0;
	int sz = G[cur].size();
	for(int i = 0; i < sz; i++) {
		int u = G[cur][i];
		if(vis[u] || u == fa) continue;
		get_root(u, cur);
		des[cur] += des[u];
		bal[cur] = max(bal[cur], des[u]);
	}
	bal[cur] = max(bal[cur], cnt-des[cur]);
	if(bal[cur] < bal[root]) root = cur;
} 

void dfs(int cur, int init, int fa) {
	cnt++;
	dist.push_back(init);
	int sz = G[cur].size();
	for(int i = 0; i < sz; i++) {
		int u = G[cur][i];
		if(vis[u] || u==fa) continue;
		dfs(u, init+L[cur][i], cur);
	}
}

int cal(int cur, int init) {
	int ans = 0;
	dist.clear();
	dfs(cur, init, -1);
	sort(dist.begin(), dist.end());
	int l = 0, r = dist.size()-1;
	while(l<r) {
		if(dist[l]+dist[r] <= k) ans += r-l, l++;
		else r--;
	}
	return ans;
}

int work(int cur) {
	int ans = 0;
	vis[cur] = 1;
	ans += cal(cur, 0);
	for(int i = 0; i < G[cur].size(); i++) {
		int u = G[cur][i];
		if(vis[u]) continue;
		cnt = 0;
		ans -= cal(u, L[cur][i]);
		root = 0; get_root(u, -1);
		ans += work(root);
	}
	return ans;
}

void init() {
	for(int i = 1; i <= n; i++) {
		G[i].clear(); L[i].clear();
	}
	memset(vis, 0, sizeof(vis));
}

int main() {
//	freopen("input.txt", "r", stdin);
	while(scanf("%d%d", &n, &k) == 2 && n) {
		init();
		for(int i = 1; i < n; i++) {
			int u, v, l; scanf("%d%d%d", &u, &v, &l);
			G[u].push_back(v); L[u].push_back(l);
			G[v].push_back(u); L[v].push_back(l);
		}
		cnt = n; root = 0; bal[0] = INF;
		get_root(1, -1);
		//cout << root << endl;
		int ans = work(root);
		printf("%d\n", ans);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

时间: 08-10

POJ 1741 Tree(树分治|ltc男人八题)的相关文章

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

【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

LCT男人八题系列

楼教的男人八题名气甚大,今天做了一道感觉还是涨了不少姿势的,然而估计之后的每道题都要看题解吧,姑且先记录一下.以后再做再更 1737 Connected Graph 1100 [email protected] 1738 An old Stone Game 407 [email protected] 1739 Tony's Tour 671 [email protected] 1740 A New Stone Game 2240 [email protected] 1741 Tree 1728