# 11629: 【原1629】Balance

### 题目描述

author: Spy 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1629

# Description

## Sample Input

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


## Sample Output

1 2


## BugenZhao's solution

//
// Created by BugenZhao on 2019/5/19.
//

#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) {
Node *ret = head->next;
while (i--) {
ret = ret->next;
}
return ret;
}

public:
N = 0;
head = new Node;
}

N = 0;
head = new Node;
auto p = other.head->next;
while (p) {
p = p->next;
}
}

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

clear();
}

int size() const {
return N;
}

void addLast(const Item &item) {
auto node = new Node(item);
tail->next = node;
tail = node;
++N;
}

void addFirst(const Item &item) {
auto tmp = head->next;
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:

Iterator(Node *head, Node *tail) :

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;
int ans = 0x7fffffff;
int index = 0x7fffffff;

int getWeight(int i, int last) {
int maxWeight = 0;
int weight = 0;
auto p = lists[i].head->next;
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 < ans) {
ans = maxWeight;
index = i;
} else if (maxWeight == ans && i < index) {
index = i;
}
return weight + 1;
}

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

cin >> n;
lists = new BLinkedList<int>[n + 1];

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

getWeight(1, 0);
cout << index << ' ' << ans << endl;
delete[] lists;
return 0;
}


## ligongzzz's solution

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

class node {
public:
int parent = 0;
int num = 1;
vector<int> child;
};

node tree_data[10009];

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

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

int n;
cin >> n;

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

dfs(1);

int ans = 999999999, ans_i = 0;;
for (int i = 1; i <= n; ++i) {
int cur_ans = n - tree_data[i].num;
for (auto p : tree_data[i].child) {
if (p != tree_data[i].parent) {
cur_ans = tree_data[p].num > cur_ans ? tree_data[p].num : cur_ans;
}
}
if (cur_ans < ans) {
ans_i = i;
ans = cur_ans;
}
}

cout << ans_i << " " << ans;

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

void clear() {
siz = 0;
delete[] x;
cap = 16;
x = new int[cap];
}
};

Vector connection[10001];
bool visited[10001];
int node_size[10001];
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 run() {
int op1, op2;
cin >> n;
for (int i = 0; i < n; i++) connection[i].clear();
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);
int min_size = node_size[0], min_idx = 0;
for (int i = 0; i < n; i++) {
if (node_size[i] < min_size) {
min_size = node_size[i];
min_idx = i;
}
}
cout << min_idx + 1 << " " << min_size << endl;
}

int main() {
run();
return 0;
}