# 14189: 【原4189】西部世界

### 题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4189

## Sample Input

8 1 2 1 3 2 4 2 5 3 6 3 7 4 8

1 2

## ligongzzz's solution

``````#include <iostream>
#include <vector>
using namespace std;

class node {
public:
int parent = 0, child_num = 0;
vector<int> child;
};

vector<node> tree_data;

int dfs(int root) {
tree_data[root].child_num = 1;
for (auto p : tree_data[root].child) {
if (p != tree_data[root].parent) {
tree_data[p].parent = root;
tree_data[root].child_num += dfs(p);
}
}
return tree_data[root].child_num;
}

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

int n;
cin >> n;

tree_data.resize(n + 1);

for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
tree_data[u].child.push_back(v);
tree_data[v].child.push_back(u);
}

dfs(1);

for (int i = 1; i <= n; ++i) {
if (n - tree_data[i].child_num > n / 2) {
continue;
}
bool flag = true;
for (auto p : tree_data[i].child) {
if (p != tree_data[i].parent) {
if (tree_data[p].child_num > n / 2) {
flag = false;
break;
}
}
}
if (flag) {
cout << i << " ";
}
}

return 0;
}
``````

## Neight99's solution

``````#include <iostream>

using namespace std;

const int maxN = 1e5 + 100;

struct Node {
int data;
Node *next;

Node(int d = 0, Node *n = 0) : data(d), next(n) {}
};

Node son[maxN] = {0};
int father[maxN] = {0}, Size[maxN] = {0}, ans[maxN] = {};
bool isNode[maxN] = {0};

int DFS(int, int);

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int N, k = 0, root;
cin >> N;
for (int i = 1; i < N; i++) {
int u, v;
cin >> u >> v;
son[u].data = u;
son[v].data = v;
ans[u] = ans[v] = 1;
if ((!isNode[u] && !isNode[v]) || (isNode[u] && !isNode[v])) {
Node *p = &(son[u]);
while (p->next != NULL) {
p = p->next;
}
p->next = new Node(v);
father[v] = u;
isNode[u] = isNode[v] = 1;
} else if (isNode[v] && isNode[u]) {
Node *p = &son[v];
while (p->next != NULL) {
p = p->next;
}
p->next = new Node(u);
father[u] = v;
isNode[u] = isNode[v] = 1;
}
}

for (int i = 1; i <= N; i++) {
if (father[i] == 0) {
root = i;
break;
}
}

DFS(root, N);

for (int i = 1; i <= N; i++) {
bool flag = 1;
Node *p = &son[i];
while (p->next != NULL) {
p = p->next;
if (Size[p->data] > N / 2) {
flag = 0;
break;
}
}
if (N - Size[i] - 1 > N / 2) {
flag = 0;
}
if (flag) {
ans[k] = i;
k++;
}
}

for (int i = 0; i < k; i++) {
cout << ans[i] << '\n';
}

return 0;
}

int DFS(int x, int N) {
if (son[x].next == NULL) {
return 1;
} else {
Node *p = &(son[x]);
while (p->next != NULL) {
p = p->next;
Size[x] += DFS(p->data, N);
}
return Size[x] + 1;
}
}
``````

## q4x3's solution

``````/**
* dfs
* 不能用vector真是太烦了
* TAT
**/
#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;
}
``````

## victrid's solution

``````#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;
}
``````