TreeDescription
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 exceed k.
Write a program that will count how many pairs which are valid for a given tree.Input
The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l.
The last test case is followed by two zeros.Output
For each test case output the answer on a single line.Sample Input
5 4
1 2 3
1 3 1
1 4 2
3 5 1
0 0Sample Output
8Source
【题意】
求树上两点间距离小等于K的方案数 （n<=10000）
【分析】
经典的点分治问题。
搞笑的我知道怎么做都纠集好久，纠结症怎么破。
每层求重心方法分治是nlogn的。
具体是，每次都只算lca为根的点对。
设dis[x]为x节点到根的距离，那么我们求dis[x]+dis[y]<=k的方案数，并且x和y要在同子树上。
先不考虑在不同子树上，直接求dis[x]+dis[y]<=k可以排序一次然后for一遍动态累加，然后再把同一棵子树上的方案数剪掉。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define Maxn 10010
#define INF 0xfffffff struct node
{
int x,y,c,next;
}t[Maxn*];int len;
int first[Maxn];
int n,k; int mymax(int x,int y) {return x>y?x:y;} void ins(int x,int y,int c)
{
t[++len].x=x;t[len].y=y;t[len].c=c;
t[len].next=first[x];first[x]=len;
}
int rt;
bool q[Maxn];
int sm[Maxn],mx[Maxn],dep[Maxn];
int v[Maxn],vl; void dfs(int x,int h,int f)
{
mx[x]=-;sm[x]=;
for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&q[t[i].y])
{
int y=t[i].y;//dep[y]=dep[x]+t[i].c;
dfs(y,h,x);
sm[x]+=sm[y];
mx[x]=mymax(mx[x],sm[y]);
}
mx[x]=mymax(mx[x],h-sm[x]);
if(mx[x]<mx[rt]) rt=x;
} int get_ans()
{
int now=,ans=;
sort(v+,v++vl);
for(int i=vl;i>=;i--)
{
if(now>i) now=i;
while(v[i]+v[now]<=k&&now<i) now++;
ans+=now-;
}
return ans;
} void dfs2(int x,int f)
{
v[++vl]=dep[x];
for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&q[t[i].y])
{
int y=t[i].y;
dep[y]=dep[x]+t[i].c;
dfs2(y,x);
}
} int fans; void ffind(int x,int f)
{
vl=;dep[x]=;dfs2(x,);
fans+=get_ans();
q[x]=;
for(int i=first[x];i;i=t[i].next) if(t[i].y!=f&&q[t[i].y])
{
int y=t[i].y;
vl=;dfs2(y,x);
fans-=get_ans();
}int i;
for(i=first[x];i;i=t[i].next)
if(t[i].y!=f&&q[t[i].y])
{
rt=;
dfs(t[i].y,x,sm[t[i].y]);
ffind(rt,x);
}
} int main()
{
while()
{
scanf("%d%d",&n,&k);
if(n==&&k==) break;
memset(first,,sizeof(first));
len=;
for(int i=;i<n;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);ins(y,x,c);
}
fans=;
memset(q,,sizeof(q));
mx[]=INF;
rt=;vl=;dfs(,n,);
ffind(rt,);
printf("%d\n",fans);
}
return ;
}
[POJ 1741]
其实不知道我打的点分治标不标准，感觉很丑。这题就有3个dfs，ffind是求分治的子树答案，dfs是求子树重心，dfs2是求dis以及把子树的dis加入到v中排序。
2016-10-16 22:16:44