11629: 【原1629】Balance

题目

题目描述

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

Description

有一棵节点编号为\(1...N\)的树，删除其中任意一个节点都会令树分裂成森林。 请你找出这样的节点（我们称之为树的重心），使得该节点被删除后，形成的森林中，节点数最多的树的节点数最少。

Input Format

第一行一个整数\(N\) 。 接下来 \(N-1\) 行，每行两个整数 \(u,v\)，表示两个节点之间存在边。

Output Format

输出一行两个整数\(c,s\)，代表树的重心和森林中最大树的节点数。

如果重心不止一个，输出序号最小的情况。

Sample Input

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

Sample Output

1 2

Limits

对于\(80\%\)的数据，\(N\in (0，1000)\)。

对于\(100\%\)的数据，\(N\in (0，10000)\)。

BugenZhao's solution

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


#ifndef SBL_BLINKEDLIST_H
#define SBL_BLINKEDLIST_H

#include <stdexcept>

template<typename Item>
class BLinkedList {
    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 *head;
    Node *tail;

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

public:
    BLinkedList() {
        N = 0;
        head = new Node;
        tail = head;
    }

    BLinkedList(const BLinkedList &other) {
        N = 0;
        head = new Node;
        tail = head;
        auto p = other.head->next;
        while (p) {
            addLast(p->item);
            p = p->next;
        }
    }

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

    virtual ~BLinkedList() {
        clear();
        delete head;
    }

    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);
        head->next = node;
        ++N;
    }

    void insert(int i, const Item &item) {
        if (i == 0)
            addFirst(item);
        else if (i == N)
            addLast(item);
        else if (i >= N || i < 0)
            throw std::out_of_range("BLinkedList::insert out_of_range");
        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)
            throw std::out_of_range("BLinkedList::get out_of_range");
        return getNode(i)->item;
    }

    void set(int i, const Item &item) {
        if (i >= N || i < 0)
            throw std::out_of_range("BLinkedList::set out_of_range");
        getNode(i)->item = item;
    }

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

        Iterator(Node *head, Node *tail) :
                it(head), head(head), tail(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 {
        return Iterator(head, tail);
    }

    friend int getWeight(int, int);
};

#endif //SBL_BLINKEDLIST_H

#include <iostream>
#include <string>

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

int n;
BLinkedList<int> *lists;
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;
        lists[a].addLast(b);
        lists[b].addLast(a);
    }

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