POJ 1741 Tree ——点分治

【题目分析】

这貌似是做过第三道以Tree命名的题目了。

听说树分治的代码都很长,一直吓得不敢写,有生之年终于切掉这题。

点分治模板题目。自己YY了好久才写出来。

然后1A了,开心o(* ̄▽ ̄*)ブ

【代码】

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define maxn 20005
#define inf 0x3f3f3f3f
using namespace std;

int n,k,h[maxn],to[maxn],ne[maxn],w[maxn],en,cnt;
int a[maxn],b[maxn],ban[maxn],siz[maxn],size,root;
int mx[maxn],now,now_mx,tot;

void init(){en=cnt=0;memset(h,-1,sizeof h);memset(ban,0,sizeof ban);}
void add(int a,int b,int c){to[en]=b;w[en]=c;ne[en]=h[a];h[a]=en++;}
void rd(){for(int i=1;i<n;++i){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}}

void dfs_size(int o,int fa)
{
	siz[o]=1;
	mx[o]=0;
	for (int i=h[o];i>=0;i=ne[i])
	if (to[i]!=fa&&!ban[to[i]]){
		dfs_size(to[i],o);
		siz[o]+=siz[to[i]];
		mx[o]=max(mx[o],siz[to[i]]);
	}
}

void dfs_root(int o,int fa)
{
	int now=max(mx[o],size-siz[o]);
	if (now<now_mx) now_mx=now,root=o;
	for (int i=h[o];i>=0;i=ne[i]) if (to[i]!=fa&&!ban[to[i]]) dfs_root(to[i],o);
}

void dfs_dist(int o,int fa,int dist)
{
	a[++tot]=dist;
	for (int i=h[o];i>=0;i=ne[i])
		if (to[i]!=fa&&!ban[to[i]])
			dfs_dist(to[i],o,dist+w[i]);
}

int cal()
{
	int ret=0,j=tot;
	sort(a+1,a+tot+1);
	for (int i=1;i<=tot;++i)
	{
		while (a[j]+a[i]>k&&j) j--;
		ret+=j;
		if (j>i) ret--;
	}
	return ret/2;
}

void dfs(int o)
{
	dfs_size(o,0);
	size=siz[o];
	now_mx=inf;
	dfs_root(o,0);
	ban[root]=1;
	for (int i=h[root];i>=0;i=ne[i])
	{
		if (!ban[to[i]])
		{
			tot=0;
			dfs_dist(to[i],root,w[i]);
			cnt-=cal();
		}
	}
	tot=0;
	dfs_dist(root,0,0);
	cnt+=cal();
	for (int i=h[root];i>=0;i=ne[i])
		if (!ban[to[i]])
			dfs(to[i]);
}

int main()
{
	while (scanf("%d%d",&n,&k)!=EOF&&n&&k)
	{
		init();rd();dfs(1);
		printf("%d\n",cnt);
	}
}

  

时间: 01-31

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

题意 给定 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(树分治)

去网上搜题解大多数都是说论文,搜了论文看了看,写的确实挺好,直接复制过来. 不过代码中有些细节还是要注意的,参考这篇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 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 树形DP(分治)

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

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

思路参考于: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 (树的分治,树的重心)

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