树分治基础模板以及树的重心（poj1741 tree）

好久没有更新博文了，这里更新一发~~

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

Sample Output

8
简单翻译一下，给定你若干条边，然后让你求任意两点之间的距离小于等于k的有多少对，暴力n^2肯定要炸，于是我们就可以想到用树分治。
我们发现总共只有2种情况，经过根节点和不经过根节点。
设d[i]为i节点到根节点的距离（注意：根节点是会变动的，因为我们每一次都要求一次重心,为了不使树退化成一条链，于是根节点就是重心节点是变动的）
d[i]+d[j]<=k就是表示经过根节点，我们发现排序之后d[i]是有序的，于是我们用两个指针在序列中进行搜索就可以了这里复杂度为on
然后求剩下不经过根节点的情况的时候我们就在他自身的子节点中同样进行上述的操作就可以了，注意要求重心！！
然后综合一下,此题使用树的分治算法时间复杂度为O(nlog^2n) 。 
接下来放上一份我抄过来的代码，明天应该还要再写一遍的~
这代码感觉思路比较的清晰，我做了一些改动。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define maxn 30000
using namespace std;
struct Node{int to,w;};
int f[maxn],sum[maxn],d[maxn],book[maxn];
int sz=0,k,n,root,ans=0;
vector<int> dep;
vector<Node> g[maxn];

void getroot(int x,int fa)
{
f[x]=0,sum[x]=1;
for(int i=0;i<g[x].size();i++)
{
int u=g[x][i].to;
if(u!=fa&&!book[u])
{
getroot(u,x);
sum[x]+=sum[u];
f[x]=max(f[x],sum[u]);
}
}
f[x]=max(f[x],sz-sum[x]);
if(f[x]<f[root])
root=x;
}

void getdep(int x,int fa)
{
dep.push_back(d[x]);
for(int i=0;i<g[x].size();i++)
{
int u=g[x][i].to,w=g[x][i].w;
if(u!=fa&&!book[u])
{
d[u]=d[x]+w;
getdep(u,x);
}
}
}

int calc(int x,int init)
{
dep.clear();d[x]=init;getdep(x,0);
sort(dep.begin(),dep.end());
int ans=0;
for(int l=0,r=dep.size()-1;l<r;)
if(dep[l]+dep[r]<=k) ans+=r-l,l++;
else r--;
return ans;
}

void work(int x)
{
ans+=calc(x,0);book[x]=1;
for(int i=0;i<g[x].size();i++)
{
int u=g[x][i].to;
if(!book[u])
{
ans-=calc(u,g[x][i].w);
f[0]=sz=sum[u];
getroot(u,root=0);
work(root);
}
}
}

int main()
{
while(cin>>n>>k&&n&&k)
{
memset(book,0,sizeof(book));
for(int i=1;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[u].push_back((Node){v,w});
g[v].push_back((Node){u,w});
}
f[0]=sz=n;
getroot(1,root=0);
ans=0;
work(root);
printf("%d\n",ans);
for(int i=1;i<=n;i++) g[i].clear();
}
return 0;
}

也就90行不算多~up++

秒客网

树分治基础模板以及树的重心（poj1741 tree）

相关文章