bzoj3365(poj 1987)点分治

几乎跟poj的1741是一样的。。。

所以就直接看这里吧

树分治其实就是分治思想在树上的应用，在这个题中具体点就是把一颗子树中的路径分别计算然后递归到子树中再经行下一步的计算直到子树只有一个点

这个操作是基于点的所以叫点分治

这个题调了好久。。。原因是在对一个子树进行分治完以后，要对重心打标记而不是对这个子树的根节点打标记!!!!!

希望大家吸取我的教训

因为是权限题所以粘过来题目

Description

Input

Output

Sample Input

Sample Output

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define MAX 40005
#pragma comment(linker, "/STACK:1024000000,1024000000")   
#define rep(i,j,k) for(int i=j;i<=k;i++)

using namespace std;

int tot=0,ans=0;
int n,m,k,to[2*MAX],next[2*MAX],head[MAX],value[2*MAX];
int u[MAX],t,size[MAX],f[MAX],done[MAX];

struct wbysr
{
	int belong,dis;
}a[MAX];

bool cmp(wbysr a1,wbysr a2)
{
	return a1.dis<a2.dis;
}

void add(int from,int To,int weight)
{
	to[++tot]=To;
	next[tot]=head[from];
	value[tot]=weight;
	head[from]=tot;
}

void dfs(int x,int fa)
{
	u[++t]=x;
	size[x]=1;
	f[x]=0;
	for(int i=head[x];i;i=next[i])
		if(!done[to[i]]&&to[i]!=fa)
			dfs(to[i],x),size[x]+=size[to[i]],f[x]=max(f[x],size[to[i]]);
	return;
}

int find_root(int x)
{
	t=0;
	dfs(x,0);
	int Min=0x7fffffff,p;
	rep(i,1,t)
		if(max(size[x]-size[u[i]],f[u[i]])<=Min)
			Min=max(size[x]-size[u[i]],f[u[i]]),p=u[i];
	return p;
}

void dfs2(int x,int fa,int Belong,int dist)
{
	a[++t].belong=Belong;
	a[t].dis=dist;
	for(int i=head[x];i;i=next[i])
		if(!done[to[i]]&&to[i]!=fa)
			dfs2(to[i],x,Belong,dist+value[i]);
	return;
}

inline void calc(int x)
{
	t=0;
	a[++t].belong=x;
	a[t].dis=0;
	for(int i=head[x];i;i=next[i])
		if(!done[to[i]])
			dfs2(to[i],x,to[i],value[i]);
	sort(a+1,a+1+t,cmp);
	int r=t,same[MAX]={0};
	rep(i,1,t)
		same[a[i].belong]++;
	rep(l,1,t)
	{
		while(a[l].dis+a[r].dis>k&&r>l)
			same[a[r].belong]--,r--;
		same[a[l].belong]--;
		if(r>l)
			ans+=r-l-same[a[l].belong];
	}
}

inline void work(int x)
{
	int root=find_root(x);
	done[root]=1;
	calc(root);
//	printf("work %d %d %d\n",x,root,ans);
	for(int i=head[root];i;i=next[i])
		if(!done[to[i]])
			work(to[i]);
	return;
}

int main()
{
	scanf("%d%d",&n,&m);
	rep(i,1,m)
	{
		int a1,a2,a3;
		char ch;
		scanf("%d%d%d %c",&a1,&a2,&a3,&ch);
		add(a1,a2,a3);
		add(a2,a1,a3);
	}
	scanf("%d",&k);
	ans=0;
	work(1);
	printf("%d\n",ans);
	return 0;
}

bzoj3365(poj 1987)点分治,布布扣,bubuko.com

bzoj3365(poj 1987)点分治

原文：http://blog.csdn.net/wbysr/article/details/23024107