设为首页 加入收藏

TOP

POJ 1741 Tree（树分治|ltc男人八题）
2015-11-21 00:55:28 来源: 作者: 【大 中 小】 浏览:1次
Tags：POJ 1741 Tree 分治 ltc 男人
??

题意：求树上距离小于等于K的点对有多少个。

思路：这道题很容易想到树分治，对于当前的根节点来说，任意两个结点之间要么过根结点，要么在一棵子树中。

那么我们dfs一次求出所有点到根结点的距离，然后用o(n)的时间判定有多少节点对符合，（判断方法稍后说）

但是这样有很多在一颗子树中的节点对我们会求重复，我们需要减去在一棵子树中结点对小于等于k的数量，也就是说，我们这一步求的是在不同子树中距离小于等于k的节点对的个数。

接下来说判定方法，将每个点到根结点的距离排序，用两个指针指向队首和队尾，当结点距离和大于k时，队尾指针减一

否则更新答案并将队首指针加一。

这道题还有一个问题样例相当好，因为假如树退化成一条链时，如果我们以任意结点为根那么递归深度将达到O(n)，将会tle

所以每次树分治时我们都要找到当前树的重心，并以重心为根继续分治。

?

#include
  
     
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
              #include
              
                #define eps 1e-6 #define LL long long #define pii (pair
               
                ) //#pragma comment(linker, /STACK:1024000000,1024000000) using namespace std; const int maxn = 10000 + 100; const int INF = 0x3f3f3f3f; int n, root, k, cnt; //root记录重心 int des[maxn], bal[maxn], vis[maxn];//des记录以该节点为祖先的后代数，bal记录以该节点为根的最大子树的节点数 vector
                
                  G[maxn], L[maxn], dist; void get_root(int cur, int fa) { des[cur] = 1; bal[cur] = 0; int sz = G[cur].size(); for(int i = 0; i < sz; i++) { int u = G[cur][i]; if(vis[u] || u == fa) continue; get_root(u, cur); des[cur] += des[u]; bal[cur] = max(bal[cur], des[u]); } bal[cur] = max(bal[cur], cnt-des[cur]); if(bal[cur] < bal[root]) root = cur; } void dfs(int cur, int init, int fa) { cnt++; dist.push_back(init); int sz = G[cur].size(); for(int i = 0; i < sz; i++) { int u = G[cur][i]; if(vis[u] || u==fa) continue; dfs(u, init+L[cur][i], cur); } } int cal(int cur, int init) { int ans = 0; dist.clear(); dfs(cur, init, -1); sort(dist.begin(), dist.end()); int l = 0, r = dist.size()-1; while(l
                 
                  
?

                  
?

                  
?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：HDU 5353(Average-贪心分果) 下一篇：Codeforces Round #Pi (Div. 2) (..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: