# 11358: 【原1358】分割树

### 题目描述

author: Kainan Wang 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1358

## Input Sample

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

## Output Sample

``````3
8
``````

## BugenZhao's solution

``````//
// Created by BugenZhao on 2019/5/8.
//

#include <stdexcept>

template<typename Item>
class Node {
public:
Item item;
Node *next;

explicit Node(const Item &item, Node *next = nullptr) : item(item), next(next) {}

explicit Node(Node *next = nullptr) : next(next) {}

virtual ~Node() = default;
};

int N;
Node *tail;

Node *getNode(int i) {
while (i--) {
ret = ret->next;
}
return ret;
}

public:
N = 0;
}

N = 0;
while (p) {
p = p->next;
}
}

void clear() {
Node *tmp;
while (p) {
tmp = p;
p = p->next;
delete tmp;
}
N = 0;
}

clear();
}

int size() const {
return N;
}

auto node = new Node(item);
tail->next = node;
tail = node;
++N;
}

auto node = new Node(item, tmp);
++N;
}

void insert(int i, const Item &item) {
if (i == 0)
else if (i == N)
else if (i >= N || i < 0)
else {
auto p = getNode(i - 1);
auto tmp = p->next;
auto node = new Node(item, tmp);
p->next = node;
++N;
}
}

const Item &get(int i) {
if (i >= N || i < 0)
return getNode(i)->item;
}

void set(int i, const Item &item) {
if (i >= N || i < 0)
getNode(i)->item = item;
}

private:
class Iterator {
Node *it;
Node *tail;
public:

bool hasNext() const {
return it != tail;
}

Item &next() {
return (it = it->next)->item;
}

const Item &next() const {
return (it = it->next)->item;
}
};

public:
Iterator iterator() const {
}

friend int getWeight(int, int);
};

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;
using ll = long long;

int n;
bool *YES;

int getWeight(int i, int last) {
int maxWeight = 0;
int weight = 0;
while (p) {
int a = p->item;
if (a != last) {
int w = getWeight(a, i);
weight += w;
if (w > maxWeight) maxWeight = w;
}
p = p->next;
}
if (n - 1 - weight > maxWeight)
maxWeight = n - 1 - weight;
if (maxWeight <= n / 2) YES[i] = true;
return weight + 1;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n;
lists = new BLinkedList<int>[n + 1];
YES = new bool[n + 1]{};

int a, b;
for (int i = 0; i < n - 1; ++i) {
cin >> a >> b;
}

getWeight(1, 0);
for (int j = 1; j <= n; ++j) {
if (YES[j]) cout << j << '\n';
}
delete[] lists;
delete[] YES;
return 0;
}
``````

## FineArtz's solution

``````/* 分割树 */
#include <iostream>
#include <cassert>
using namespace std;

const int MAXN = 200000;

int head[MAXN + 5] = {0}, ed[MAXN * 2 + 5] = {0}, nxt[MAXN * 2+ 5] = {0}, cnt = 0;
int sum[MAXN + 5] = {0}, fa[MAXN + 5] = {0};
int h[MAXN + 5] = {0}, e[MAXN + 5] = {0}, nx[MAXN + 5] = {0}, m = 0;
int n;
bool b[MAXN + 5] = {0};

++cnt;
ed[cnt] = v;
}

++m;
nx[m] = h[u];
e[m] = v;
h[u] = m;
}

int buildTree(int x){
sum[x] = 1;
for (int i = head[x]; i != 0; i = nxt[i]){
if (!b[ed[i]]){
int k = ed[i];
b[k] = true;
fa[k] = x;
sum[x] += buildTree(k);
}
}
return sum[x];
}

bool check(int x){
int k = sum[1] - sum[x];
if (k > n / 2)
return false;
for (int i = h[x]; i != 0; i = nx[i]){
if (sum[e[i]] > n / 2)
return false;
}
return true;
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
}
b[1] = true;
buildTree(1);
for (int i = 1; i <= n; ++i){
if (check(i)){
cout << i << '\n';
}
}
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
#include "cstring"
using namespace std;

class edge {
public:
int val = 0;
edge* next = nullptr;
};

edge* edges_start[10009];
edge* edges_end[10009];

int nums[10009] = { 0 };
bool visited[10009] = { 0 };

int dfs(int pos) {
visited[pos] = true;
nums[pos] = 1;

for (auto p = edges_start[pos]->next; p; p = p->next) {
if (!visited[p->val]) {
nums[pos] += dfs(p->val);
}
}

return nums[pos];
}

int main() {
int n;
scanf("%d", &n);

for (int i = 1; i <= n; ++i) {
edges_start[i] = edges_end[i] = new edge;
}

for (int i = 0; i < n - 1; ++i) {
int a, b;
scanf("%d %d", &a, &b);

edges_end[a]->next = new edge;
edges_end[a] = edges_end[a]->next;
edges_end[a]->val = b;

edges_end[b]->next = new edge;
edges_end[b] = edges_end[b]->next;
edges_end[b]->val = a;
}

dfs(1);

for (int i = 1; i <= n; ++i) {
if (n - nums[i] > n / 2)
continue;
bool flag = true;
for (auto p = edges_start[i]->next; p; p = p->next) {
if (nums[p->val]<nums[i] && nums[p->val]>n / 2) {
flag = false;
break;
}
}
if (flag) {
printf("%d\n", i);
}
}

return 0;
}
``````

## q4x3's solution

``````#include <iostream>

using namespace std;

int map[100233][100], sonnum[100233];
int N, tmp1, tmp2, siz[100233], vis[100233];

int dfs(int rt) {
siz[rt] = 1;
vis[rt] = 1;
for(int i = 1;i <= sonnum[rt];++ i) {
if(! vis[map[rt][i]]) {
siz[rt] += dfs(map[rt][i]);
}
}
return siz[rt];
}

bool check(int num) {
if(N - siz[num] > (N >> 1)) return 0;
for(int i = 1;i <= sonnum[num];++ i) {
if(siz[map[num][i]] < siz[num] && siz[map[num][i]] > (N >> 1)) return 0;
}
return 1;
}

int main() {
scanf("%d", &N);
for(int i = 0;i < N - 1;++ i) {
scanf("%d%d", &tmp1, &tmp2);
map[tmp1][++ sonnum[tmp1]] = tmp2;
map[tmp2][++ sonnum[tmp2]] = tmp1;
}
dfs(1);
for(int i = 1;i <= N;++ i) {
if(check(i)) printf("%d ", i);
}
printf("\n");
return 0;
}

``````

## skyzh's solution

``````#include <iostream>
#include <cstring>

using namespace std;

struct Vector {
int cap;
int siz;
int *x;

Vector(int cap = 16) : cap(cap) {
x = new int[cap];
}

void expand() {
if (cap == siz) {
int *buffer = new int[cap * 2];
memcpy(buffer, x, sizeof(int) * cap);
cap *= 2;
delete[] x;
x = buffer;
}
}

void append(int d) {
expand();
x[siz++] = d;
}
};

Vector connection[10000];
bool visited[10000];
int node_size[10000];
int n;

int traverse(int root, int size) {
if (visited[root]) return 0;
visited[root] = true;
int d = 0;
int sum = 0;
for (int i = 0; i < connection[root].siz; i++) {
int child = connection[root].x[i];
int node_cnt = traverse(child, size + 1);
sum += node_cnt;
d = max(d, node_cnt);
}
d = max(d, n - sum - 1);
node_size[root] = d;
return sum + 1;
}

int main() {
cin >> n;
int op1, op2;
for (int i = 0; i < n - 1; i++) {
cin >> op1 >> op2;
--op1; --op2;
connection[op1].append(op2);
connection[op2].append(op1);
}
memset(visited, 0, sizeof(visited));
traverse(0, 0);
for (int i = 0; i < n; i++) {
if (node_size[i] <= n / 2) {
cout << i + 1 << endl;
}
}
return 0;
}
``````

## victrid's solution

``````//?4189?
#include <cstdio>
#include <iostream>
using namespace std;
struct ln {
int pos;
ln* next;
};

ln lis[1000005];
int sz[1000005]     = {0};
int parent[1000005] = {0};

int DFS(int pos) {
sz[pos] = 1;
ln* nx  = &lis[pos];
while (nx->next != NULL) {
nx = nx->next;
if (parent[pos] != nx->pos) {
parent[nx->pos] = pos;
sz[pos] += DFS(nx->pos);
}
}
return sz[pos];
}

int main() {
int N, p, q;
scanf("%d", &N);
for (int i = 1; i < N; i++) {
scanf("%d%d", &p, &q);
lis[p].pos = p;
lis[q].pos = q;
ln* pp     = &lis[p];
while (pp->next != nullptr) {
pp = pp->next;
}
pp->next = new ln{q, nullptr};
ln* qp   = &lis[q];
while (qp->next != nullptr) {
qp = qp->next;
}
qp->next = new ln{p, nullptr};
}
DFS(1);
//Only one needed. I'm blind.
for (int i = 1; i <= N; ++i) {
if (N - sz[i] > N / 2) {
continue;
}
bool flag = true;
ln* nx    = &lis[i];
while (nx->next != NULL) {
nx = nx->next;
if (parent[i] != nx->pos) {
if (sz[nx->pos] > N / 2) {
flag = false;
break;
}
}
}
if (flag) {
printf("%d ", i);
}
}
return 0;
}
``````

## WashSwang's solution

``````#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int x,y,n,num=1,ans,ansset[300000],last[300000],to[300000],ne[300000],son[300000];
bool vis[300000];
to[num]=v;
ne[num]=last[u];
last[u]=num;
num++;
}
void find(int x){
bool fea=true;
vis[x]=true;
for (int i=last[x];i;i=ne[i])
if (!vis[to[i]]){
find(to[i]);
if (son[to[i]]>n/2) fea=false;
son[x]+=son[to[i]];
}
if (n-son[x]>n/2) fea=false;
if (fea) ansset[ans++]=x;
}
int main() {
scanf("%d",&n);
for (int i=0;i<n-1;++i){
scanf("%d%d",&x,&y);
}
for (int i=1;i<=n;++i) son[i]=1;
find(1);
sort(ansset,ansset+ans);
for (int i=0;i<ans;++i)
printf("%d\n",ansset[i]);
return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#define MAX_N 100010
using namespace std;

int n;
int connect[MAX_N][210], length[MAX_N], seg[MAX_N][210];
bool caled[MAX_N];

int getComponent(int s, int x) {
int len = length[x];
int res = 1;
if (caled[x]) {
for (int i = 0; i < len; ++i) if (connect[x][i] != s)
res += seg[x][i];
}
else {
int tmp = 0;
for (int i = 0; i < len - 1; ++i) {
seg[x][i] = getComponent(x, connect[x][i]);
tmp += seg[x][i];
if (connect[x][i] != s)
res += seg[x][i];
}
seg[x][len - 1] = n - 1 - tmp;
caled[x] = true;
}
return res;
}

int main() {

ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
connect[x][length[x]++] = y;
connect[y][length[y]++] = x;
}
for (int i = 1; i <= n; ++i)
if (length[i] == 1) {
seg[i][0] = n - 1;
caled[i] = true;
}
for (int i = 1; i <= n; ++i)
if (length[i] == 2) {
if (length[connect[i][0]] == 1) {
seg[i][0] = 1; seg[i][1] = n - 2;
caled[i] = true;
}
if (length[connect[i][1]] == 1) {
seg[i][1] = 1; seg[i][0] = n - 2;
caled[i] = true;
}
}

for (int i = 1; i <= n; ++i)
if (!caled[i]) {
int len = length[i], tmp = 0;
for (int j = 0; j < len - 1; ++j) {
seg[i][j] = getComponent(i, connect[i][j]);
tmp += seg[i][j];
}
seg[i][len - 1] = n - 1 - tmp;
caled[i] = true;
}

for (int i = 1; i <= n; ++i) {
bool flag = true;
for (int j = 0; j < 3; ++j)
if (seg[i][j] > n >> 1) {
flag = false;
break;
}
if (flag) cout << i << endl;
}
return 0;
}
``````