Skip to content

11358: 【原1358】分割树

题目

题目描述

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

Description

现在有一棵树T,有N个节点,我们想通过去掉一个节点p来把T分割成更小的树,并且满足每个小树中的节点数不超过n/2。

请根据输入的树来输出所有可能的p的号码。

Input Format

第1行:一个整数N,代表有N个节点,且每个节点的编号为1,2,...,N。

第2~N行:每行两个整数x,y,代表节点x和节点y之间连通。

Output Format

从小到大一次输出满足条件的p的号码,每行1个可行解。

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

样例解释

当3号节点/8号节点被删除,此时剩下的树的节点数分别为2、2、5,均不大于10/2=5,而其他的节点中,无论哪一个,总有一棵树的大小大于等于6。

BugenZhao's solution

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

#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;
bool *YES;

int getWeight(int i, int last) {
    int maxWeight = 0;
    auto p = lists[i].head->next;
    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;
        lists[a].addLast(b);
        lists[b].addLast(a);
    }

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

void addEdge(int u, int v){
    ++cnt;
    nxt[cnt] = head[u];
    ed[cnt] = v;
    head[u] = cnt;
}

void addedge(int u, int 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;
            addedge(x, k);
            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;
        addEdge(u, v);
        addEdge(v, u);
    }
    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;
}
提交者 519021910876 陶青筱 那当然是救实验报告了毕竟花的时间更长啊🙂
题目编号 1358 
语言C++
提交时间2020-06-04 21:14:30

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];
void add(int u,int v){
    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);
        add(x,y);
        add(y,x);
    }
    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;
}