树的点分治
可以看09年漆子超论文,说的很详细.
Tree
Time Limit:1000MSMemory Limit:30000K
Total Submissions:12650Accepted:4025
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 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 41 2 31 3 11 4 23 5 10 0
Sample Output
8
Source
LouTiancheng@POJ
/* ***********************************************Author:CKbossCreated Time :2015年04月24日 星期五 09时37分44秒File Name:POJ1741_2.cpp************************************************ */#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>#include <cstdlib>#include <vector>#include <queue>#include <set>#include <map>using namespace std;const int INF=0x3f3f3f3f;const int maxn=10100;struct Node { int to,len; };int n,K;vector<Node> G[maxn];bool done[maxn];int size,root;int s[maxn],f[maxn],d[maxn];vector<int> dep;int ans;void findRoot(int u,int fa){s[u]=1; f[u]=0;int rest=0;for(int i=0,sz=G[u].size();i<sz;i++){int v=G[u][i].to;if(v==fa||done[v]) continue;findRoot(v,u);rest+=s[v];f[u]=max(f[u],s[v]);}s[u]+=rest;f[u]=max(f[u],size-s[u]);if(f[u]<f[root]) root=u;}void getDeep(int u,int fa){dep.push_back(d[u]);s[u]=1;for(int i=0,sz=G[u].size();i<sz;i++){int v=G[u][i].to;if(v==fa||done[v]) continue;int len=G[u][i].len;d[v]=d[u]+len;getDeep(v,u);s[u]+=s[v];}}int calc(int u,int init){dep.clear(); d[u]=init;getDeep(u,-1);sort(dep.begin(),dep.end());int ret=0;for(int l=0,r=dep.size()-1;l<r;){if(dep[l]+dep[r]<=K) ret+=r-l++;else r–;}return ret;}void solve(int u){ans+=calc(u,0);done[u]=true;for(int i=0,sz=G[u].size();i<sz;i++){int v=G[u][i].to;if(done[v]) continue;int len=G[u][i].len;ans-=calc(v,len);// 递归子树size=s[v]; root=0; findRoot(v,u);solve(root);}}int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);f[0]=INF;while(scanf("%d%d",&n,&K)!=EOF){if(n==0&&K==0) break;memset(done,false,sizeof(done));for(int i=0;i<=n+10;i++) G[i].clear();for(int i=0;i<n-1;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);G[a].push_back((Node){b,c});G[b].push_back((Node){a,c});}size=n; ans=0;findRoot(1,-1);solve(root);printf("%d\n",ans);}return 0;}
，所有的失败，与失去自己的失败比起来，更是微不足道
