SOJ 1140. 国王的遗产

题目大意：给定一棵n个顶点，n-1条边的树。有k个孩子，前k-1个孩子切走树中顶点数不大于n/2的最大连通块，剩余的结点组成新的树。最后一个孩子得到剩余的树中的所有结点。

按顺序输出每个孩子能获得的顶点数。

解题思路：任选一结点作为根节点，使用深度优先搜索，获得相对于父节点一端，子节点一端的节点总数和节点最小值。再次使用深度优先搜索，反向求得相对于子节点一端，父节点一端的节点总数和节点最小值。如此能快速获取任意边两端的节点总数和节点最小值。只需要遍历边即可，可以优化。

注意：需要证明，任意两种切法中，任意顶点不可能存在于两个合法长度相等的序列中。

代码如下：

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <ctime>
  4 #include <climits>
  5 #include <vector>
  6 #include <map>
  7 using namespace std;
  8 
  9 typedef pair<int, int> P;
 10 
 11 struct Info {
 12     int nodeMinimal;
 13     int nodeCount;
 14 };
 15 
 16 const int maxn = 30001;
 17 
 18 map<int, Info> G[maxn];
 19 
 20 P search(int cur, int upper) {
 21     map<int, Info> &near = G[cur];
 22 
 23     int minimal = INT_MAX;
 24     int count = 0;
 25     map<int, Info>::iterator iter = near.begin();
 26     while (iter != near.end()) {
 27         if (iter->first != upper) {    // 如果不是上一层的结点，就往下搜索
 28             pair<int, int> p = search(iter->first, cur);    // p.first表示下一层的总结点数，p.second表示下一层的最小值
 29             iter->second.nodeCount = p.first;
 30             iter->second.nodeMinimal = p.second;
 31             count += p.first;
 32             minimal = minimal < p.second ? minimal : p.second;
 33         }
 34         ++iter;
 35     }
 36 
 37     return P(count + 1, minimal < cur ? minimal : cur);
 38 
 39 }
 40 
 41 void reverse_search(int cur, int upper, int upper_count, int upper_minimal, int tot) {
 42     // 考虑第一个起点和最底层点
 43     if (upper != -1) {
 44         Info & info = G[cur][upper];    // 反向标记
 45         info.nodeCount = upper_count;
 46         info.nodeMinimal = upper_minimal;
 47     }
 48     // 邻结点只有一个或者多个
 49     map<int, Info> &near = G[cur];
 50     if (near.size() == 1 && upper != -1) return;    // 如果邻结点只有upper，则不需要往下递归
 51     // 如果邻结点有两个或两个以上
 52     // 找最小值和次小值
 53     int most_minimal = INT_MAX, minimal = INT_MAX;
 54     map<int, Info>::iterator iter = near.begin();
 55     while (iter != near.end()) {
 56         int nodeMinimal = iter->second.nodeMinimal;
 57         if (nodeMinimal < most_minimal) {
 58             minimal = most_minimal;
 59             most_minimal = nodeMinimal;
 60         } else if (nodeMinimal < minimal) {
 61             minimal = nodeMinimal;
 62         }
 63         ++iter;
 64     }
 65     if (cur < most_minimal) {
 66         minimal = most_minimal;
 67         most_minimal = cur;
 68     } else if (cur < minimal) {
 69         minimal = cur;
 70     }
 71 
 72 
 73     // 遍历邻结点（ != upper），如果
 74     iter = near.begin();
 75     while (iter != near.end()) {
 76         if (iter->first != upper) {    // 如果邻结点不是Upper结点，则可以继续递归搜索
 77             int cur_count = tot - iter->second.nodeCount;
 78             int cur_minimal = iter->second.nodeMinimal == most_minimal ? minimal : most_minimal;
 79             reverse_search(iter->first, cur, cur_count, cur_minimal, tot);
 80         }
 81         ++iter;
 82     }
 83 
 84 }
 85 
 86 void findCutWay(const int & cur, const int & upper, int & from, int & to, int &nodeCount, int &nodeMinimal, const int & tot) {
 87     int half_tot = tot / 2;    // 总数的一半
 88     map<int, Info> & near = G[cur];
 89     map<int, Info>::iterator iter = near.begin();
 90     while (iter != near.end()) {
 91         if (iter->second.nodeCount <= half_tot) {    // 如果相邻块数量符合要求，则操作
 92             if (iter->second.nodeCount > nodeCount) {
 93                 from = cur, to = iter->first;
 94                 nodeCount = iter->second.nodeCount;
 95                 nodeMinimal = iter->second.nodeMinimal;
 96             } else if (iter->second.nodeCount == nodeCount){
 97                 // 假设不出现nodeMinimal == iter->second.nodeMinimal的情况
 98                 nodeMinimal = nodeMinimal < iter->second.nodeMinimal ? nodeMinimal : (from = cur, to = iter->first,iter->second.nodeMinimal);
 99             }
100             if (iter->second.nodeCount == half_tot && iter->first != upper) // 如果刚好一半，要测试另一侧，可简化；如果少于一半，则不继续递归
101                 findCutWay(iter->first, cur, from, to, nodeCount, nodeMinimal, tot);
102         } else if (iter->first != upper) {
103             findCutWay(iter->first, cur, from, to, nodeCount, nodeMinimal, tot);
104         }
105         ++iter;
106     }
107 }
108 
109 void cut(int & root, int &num, int tot) {
110     // 从root开始处理整棵树并做标记 G[from][to].nodeCount , G[from][to].nodeMinimal
111     search(root, -1);
112 
113     // 把剩余的标记 : 反向标记
114     reverse_search(root, -1, 0, INT_MAX, tot);
115 
116     // 遍历整棵树，找到可以切的位置
117     int from, to, nodeCount = 0, nodeMinimal = INT_MAX;
118     findCutWay(root, -1, from, to, nodeCount, nodeMinimal, tot);
119 
120     // 真正切
121     G[from].erase(to);
122     G[to].erase(from);
123     root = from;
124     num = nodeCount;
125 }
126 
127 int main() {
128     int n, k;
129     scanf("%d%d", &n, &k);
130     int a, b;
131     for (int i = 1; i < n; ++i) {
132         scanf("%d%d", &a, &b);
133         G[a][b];
134         G[b][a];
135     }
136     // srand(rand());
137     int root = rand() % n + 1;    // 随机生成根节点
138 
139     int num;
140     int sum = 0;
141     vector<int> ans;
142     while (--k, k) {    // 对金块链 切k-1次
143         cut(root, num, n - sum);
144         sum += num;
145         ans.push_back(num);
146         // 如果剩余的少于2，则给下一位，并且退出
147         if (n - sum < 2) {
148             break;
149         }
150     }
151 
152     // ans.push_back() 剩下的连通图  n - 前面的总和
153     ans.push_back(n - sum);
154     for (int i = 1; i < k; ++i) ans.push_back(0);
155 
156     // 输出结果
157     for (int i = 0; i < ans.size(); ++i) {
158         printf("%d%c", ans[i], i == ans.size() - 1 ? '
' : ' ');
159     }
160 
161     return 0;
162 }