POJ 1741 Tree （树的分治，树的重心）

题意：给一棵树，n个节点，给定一个数k，求任意满足dist(a,b)<=k的点对的数量。

思路：

　　这道题的思路比较简单，但是细节很多。

　　此题可以用分治法，如何分治？

　　（1）如果path(a,b)不经过根，那么肯定在根的某棵子树下，递归解决。

　　（2）如果path(a,b)经过根，那么肯定在根的不同子树下，处理它。

　　怎样处理？如果知道了每棵子树中的节点到根的距离，暂且将每棵子树的节点分到每个独立的桶里。每个节点都可以和其他桶里的点组成点对，只要距离<=k的话就满足要求了。逐个算可能超时了，用个简单点的方法。在这里我们不需要知道节点是谁，只需要知道距离，所以将所有节点到根的距离取出来，排个序，用两个指针在线性复杂度就可以解决本节点下的点对统计了。

　　但是如何去重？因为所有子树中的节点全部都混着排序了，估计会有挺多对是在同棵子树下的节点被统计到了，这暂时不需要，这是要递归解决的，那么就要去掉这些同棵树下的点对。计算的方法都是一样的。

　　但是还有一种情况让你TLE，就是单链时的情况，若每次以孩子来递归下去解决，可能就不行了。但是可以发现到，计算这棵子树时，完全也不用经过根，那么不妨直接找出这棵子树中的重心作为根来解决这个子问题。复杂度主要是在排序的地方，用了找重心的方法可以保证每个点最多被排序2*logn次，所以总复杂度为O(nlog²n)。

　　如下图，红色点为重心，红色的线为虚拟边。左图是原树，右图是分治的过程。就像是每个重心隔开了一些子树一样。

　　有论文可以看。

 //#include <bits/stdc++.h>

 #include <vector>

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 #define LL long long

 using namespace std;

 const int N=;

 int n, k, root, edge_cnt, ans, num, big, vis[N];

 vector<int> vect[N];

 struct node

 {

     int from,to,len;

     node(){};

     node(int from,int to,int len):from(from),to(to),len

 (len){};

 }edge[N*];

 void add_edge(int from,int to,int len)

 {

     edge[edge_cnt]=node(from,to,len);

     vect[from].push_back(edge_cnt++);

 }

 int get_size(int t,int far)

 {

     int cnt=;

     for(int i=; i<vect[t].size(); i++)

     {

         node e=edge[vect[t][i]];

         if(e.to!=far&&!vis[e.to])    cnt+=get_size(e.to, t);

     }

     return cnt;

 }

 int get_root(int t,int far)   //求重心:root。

 {

     int cur=, sum=;

     for(int i=; i<vect[t].size(); i++)

     {

         node e=edge[vect[t][i]];

         if( e.to!=far && !vis[e.to] )

         {

             int tmp=get_root(e.to, t);

             sum+=tmp;

             cur=max(cur, tmp);

         }

     }

     cur=max(cur, num-sum);

     if(cur<big)     big=cur, root=t;    //更新root

     return sum;

 }

 vector<int> seq;

 void get_all(int t,int far,int len)     //获取子树t的所有节点

 {

     seq.push_back(len);

     if(len>=k)   return ;   //剪枝

     for(int i=; i<vect[t].size(); i++)

     {

         node e=edge[vect[t][i]];

         if( !vis[e.to] && e.to!=far )    get_all(e.to, t, len+e.len);

     }

 }

 int cal(int t,int len)      //计算子树t的内部点对。

 {

     seq.clear();

     get_all(t, , len);     //将以t为根的整棵子树的len装进去seq

     sort(seq.begin(), seq.end());

     int tmp=, L=, R=seq.size()-;

     while( L<R )

     {

         if( seq[L]+seq[R]<=k )    tmp+=R-L,L++;

         else    R--;

     }

     return tmp;

 }

 void solve(int t)    //主函数

 {

     vis[t]=;

     ans+=cal(t, );         //计算子树t的答案

     for(int i=; i<vect[t].size(); i++)

     {

         node e=edge[vect[t][i]];

         if( !vis[e.to] )

         {

             ans-=cal(e.to, e.len);  //去重

             big=INF;root=-;num=get_size(e.to, -); //用于找重心

             get_root(e.to, -);

             solve(root);

         }

     }

 }

 void init()

 {

     for(int i=; i<=n; i++)vect[i].clear();

     memset(vis, , sizeof(vis));

     ans=edge_cnt=;

 }

 int main()

 {

     //freopen("input.txt", "r", stdin);

     int a,b,c;

     while( scanf("%d%d",&n,&k), n+k  )

     {

         init();

         for(int i=; i<n; i++)

         {

             scanf("%d%d%d",&a,&b,&c);

             add_edge(a,b,c);

             add_edge(b,a,c);

         }

         num=n;big=INF;root=-;  //找重心用的。

         get_root(,-);         //找重心

         solve( root );

         printf("%d\n", ans);

     }

     return ;

 }

AC代码

巴特西

POJ 1741 Tree （树的分治，树的重心）

最新文章

热门文章