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 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

题解

求树上总共有多少点对(u,v)距离<=k

题意

初学点分治

树的重心定义：找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡

点分治就是把树按子树重心不断DFS，然后处理每个子树对答案的贡献，会用到容斥，把n^2的复杂度优化为nlogn

处理每个子树对答案的贡献，先求出重心到各个点的距离，然后sort一下，然后可以二分出满足<=k的答案

代码

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<vector>
  4 #include<algorithm>
  5 using namespace std;
  6 
  7 const int maxn=1e4+5;
  8 
  9 vector< pair<int,int> >G[maxn];
 10 int mx[maxn],size[maxn],vis[maxn],dis[maxn],ans,MIN,n,k,num,root;
 11 void dfssize(int u,int fa)
 12 {
 13     size[u]=1;
 14     mx[u]=0;
 15     for(int i=0;i<G[u].size();i++)
 16     {
 17         int v=G[u][i].first;
 18         if(!vis[v]&&v!=fa)
 19         {
 20             dfssize(v,u);
 21             size[u]+=size[v];
 22             mx[u]=max(mx[u],size[v]);
 23         }
 24     }
 25 }
 26 void dfsroot(int r,int u,int fa)//r为子树的根 
 27 {
 28     if(size[r]-size[u]>mx[u])//子树的其余节点 
 29         mx[u]=size[r]-size[u];
 30     if(mx[u]<MIN)//root为重心
 31         MIN=mx[u],root=u;
 32     for(int i=0;i<G[u].size();i++)
 33     {
 34         int v=G[u][i].first;
 35         if(!vis[v]&&v!=fa)
 36             dfsroot(r,v,u);
 37     }
 38 }
 39 void dfsdis(int u,int fa,int d)
 40 {
 41     dis[num++]=d;
 42     for(int i=0;i<G[u].size();i++)
 43     {
 44         int v=G[u][i].first;
 45         int w=G[u][i].second;
 46         if(!vis[v]&&v!=fa)
 47             dfsdis(v,u,d+w);
 48     }
 49 }
 50 int cal(int r,int w)
 51 {
 52     int ret=0;
 53     num=0;
 54     dfsdis(r,r,w);
 55     sort(dis,dis+num);
 56     int L=0,R=num-1;
 57     while(L<R)
 58     {
 59         while(dis[L]+dis[R]>k&&L<R)R--;
 60         ret+=R-L;    
 61         L++;
 62     }
 63     return ret;
 64 }
 65 void dfs(int u)
 66 {
 67     MIN=n;
 68     dfssize(u,u);
 69     dfsroot(u,u,u);
 70     int Grivate=root;
 71     ans+=cal(Grivate,0);
 72     vis[root]=1;
 73     for(int i=0;i<G[Grivate].size();i++)
 74     {
 75         int v=G[Grivate][i].first;
 76         int w=G[Grivate][i].second;
 77         if(!vis[v])
 78         {
 79             ans-=cal(v,w);
 80             dfs(v);
 81         }
 82     }
 83 }
 84 int main()
 85 {
 86     while(scanf("%d%d",&n,&k)!=EOF,n||k)
 87     {
 88         ans=0; 
 89         for(int i=1;i<=n;i++)
 90         {
 91             G[i].clear();
 92             vis[i]=0;
 93         }
 94         for(int i=1,u,v,w;i<n;i++)
 95         {
 96             scanf("%d%d%d",&u,&v,&w);
 97             G[u].push_back({v,w});
 98             G[v].push_back({u,w});
 99         }
100         dfs(1);
101         printf("%d\n",ans);
102     }
103     return 0;
104 }

秒客网

POJ 1741 Tree(点分治点对

相关文章