POJ1741――Tree 基于点的分治 - c++编程基础

Tree

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 11229		Accepted: 3515

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

Source

LouTiancheng@POJ

这题要我们计算所有满足距离之和小于等于k的点对的数目， n最大有10000，显然O(n^2)的做法是行不通的，看了部分09年漆子超《分治算法在树的路径问题中的应用》，于是试着去理解这种做法，然后写下了这篇博客。

显然我们可以知道，这样的点对可以分为2种
1) 经过树的根
2)在某一棵子树里面

而2显然可以递归处理，所以我们把目光放在1

我们设dist[i]表示点i到根的距离，那么我们1要求的就是 dist[i] + dist[j] <= k && i,j 属于不同的子树，从论文中我们可以学到，把所要求的转化为dist[i] + dist[j] <= k的所有点对减去dist[i] + dist[j] <= k && i,j处在同一个子树里的点对，这就是我们要求的东西

而统计点对数，我们可以在O(n)的时间内完成，操作就是给数组排个序，然后左边，右边分别移动下标，边移动边统计就OK了，复杂度O(n*logn)

接下来还有一个问题，如果这个树是一条链，那么每次去递归子树，复杂度显然会到达O(n^2)，所以这里又要引出一个内容：树的重心

树的重心是这样定义的：删掉重心以后，树被分为几个部分，使得那几个部分里点最多的那个部分的点数最少

树的重心我们可以通过树形dp在O(n)时间里求得，可以证明，如果每次都选取子树的重心作为根，那么递归次数最多不超过logn次，所以整个过程下来，复杂度是O(n*logn*logn)

先放上我的代码吧，也是结合了网上各个前辈的做法的
PS：我还想在代码下面写点关于代码理解的

#include 
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              using namespace std; const int N = 10010; const int inf = 0x3f3f3f3f; int num[N]; int head[N]; int dist[N]; int dp[N]; bool vis[N]; struct node { int weight; int next; int to; }edge[N << 1]; int tot, root, n, k, size, res, ans; void addedge(int from, int to, int weight) { edge[tot].weight = weight; edge[tot].to = to; edge[tot].next = head[from]; head[from] = tot++; } void get_root(int u, int fa) { num[u] = 1; dp[u] = 0; for (int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to; if (v == fa || vis[v]) //-------------------------A { continue; } get_root(v, u); num[u] += num[v]; dp[u] = max(dp[u], num[v]); } dp[u] = max(dp[u], size - num[u]); if (dp[u] < dp[root]) { root = u; } } void calc_dist(int u, int fa, int d) { dist[res++] = d; for (int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to; if (v == fa || vis[v])//--------------------------B { continue; } calc_dist(v, u, d + edge[i].weight); } } int counts(int u, int d) { res = 0; calc_dist(u, -1, d); int ans = 0; sort(dist, dist + res); int i = 0; int j = res - 1; while (i < j) { while (i < j && dist[i] + dist[j] > k) { j--; } ans += j - i; i++; } return ans; } void solve(int u) { ans += counts(root, 0); vis[root] = 1; for (int i = head[root]; ~i; i = edge[i].next) { int v = edge[i].to; if (vis[v]) { continue; } ans -= counts(v, edge[i].weight); // ------------------------------C root = 0; dp[0] = size = num[v]; get_root(v, -1); solve(v); } } int main() { int u, v, w; while (~scanf("%d%d", &n, &k)) { if (!n && !k) { break; } memset ( head, -1, sizeof(head) ); memset ( num, 0, sizeof(num) ); memset ( vis, 0, sizeof(vis) ); tot = 0; ans = 0; for (int i = 0; i < n - 1; ++i) { scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); addedge(v, u, w); } root = 0; dp[root] = size = n; get_root(1, -1); solve(1); printf("%d\n", ans); } return 0; }

先来解释下注释C吧，

ans -= counts(v, edge[i].weight);

为什么是edge[i].weight而不是0，今天看的时候不知道是不是脑子短路了一直没理解，其实是这样的，root(当前树根)这棵树统计完了点对以后，其实已经包含了某些点对，它们处在同一个子树里，但是距离和确实小于等于k的，那么这里小于等于k是基于它们到点root的，所以在处理v这个子树的时候，我们需要把这样的点对给去掉，那么基准点当然还是以root为主，这样才能准确地去掉这些点对，所以要加上root --- v这条边上的权值

再来看A和B，为什么要加一个fa，由于建立的是无向边，所以得加一个fa，放止从子树跑到根上去
vis数组是为了防止访问到已经处理过的重心（子树的根），我们每次找到一个重心，要拿它当根来处理的时候，都会把它标记为已经访问过，如果不慎访问到了已经访问过的root（即子树），那么分治就被干扰了，或者说已经被破坏了，所以这个vis数组是一定要加上去的
基本就讲到这里，如果发现本人所写有错误，欢迎给我留言