# 14298: 【原4298】分割海岛

### 题目描述

author: Online Judge 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4298

## 样例输入1

``````10 5
1 7
4 7
6 1
8 4
9 4
5 6
2 1
3 1
10 8
``````

## 样例输出1

``````7 1
``````

## HINT

• 包括头文件`algorithm`
• 在命名空间内有`sort(begin, end)`函数, 其中`begin``end`分别为排序开始的位置和结束的位置(左闭右开). 特别地, 如果想要让`arr`数组中下标为`i`至下标`j`之间(左闭右开)的元素从小到大排列的话, 可以调用`sort(arr + i, arr + j)`

``````#include <algorithm>
using namespace std;
int a[] = {3, 4, 1, 2};
int main() {
sort(a + 1, a + 3);
// 此时 a = {3, 1, 4, 2}
sort(a, a + 4);
// 此时 a = {1, 2, 3, 4}
return 0;
}
``````

## zqy2018's solution

``````#include <cstdio>
#include <algorithm>
#define INF 2000000000
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, k;
int to[200005], at[100005], nxt[200005], cnt = 0;
int ans[100005], tot = 0;
int dfs(int cur, int fa){
int maxi = 0, siz = 1;
for (int i = at[cur]; i; i = nxt[i]){
int v = to[i];
if (v == fa) continue;
int dd = dfs(v, cur);
siz += dd;
maxi = max(maxi, dd);
}
maxi = max(maxi, n - siz);
if (maxi <= k) ans[++tot] = cur;
return siz;
}
void init(){
for (int i = 1; i < n; ++i){
to[++cnt] = v, nxt[cnt] = at[u], at[u] = cnt;
to[++cnt] = u, nxt[cnt] = at[v], at[v] = cnt;
}
}
void solve(){
dfs(1, 0);
if (tot == 0){
printf("None\n");
}else {
sort(ans + 1, ans + tot + 1)    ;
for (int i = tot; i > 1; --i)
printf("%d ", ans[i]);
printf("%d\n", ans[1]);
}

}
int main(){
init();
solve();
return 0;
}
``````