求助:90分,WA第一个点
  • 板块P1395 会议
  • 楼主异想之旅
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/10/23 10:10
  • 上次更新2023/10/27 06:22:29
查看原帖
求助:90分,WA第一个点
353878
异想之旅楼主2022/10/23 10:10
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5;

int n;

struct EDGE {
    int v, next;
} edge[N << 1];
int ecnt, head[N];
void adde(int u, int v) {
    edge[++ecnt] = (EDGE){v, head[u]};
    head[u] = ecnt;
    edge[++ecnt] = (EDGE){u, head[v]};
    head[v] = ecnt;
}

int maxx[N];
bool visit[N];

int dfs(int x) {
    visit[x] = 1;
    int s = 0;
    for (int i = head[x]; i; i = edge[i].next) {
        const int v = edge[i].v;
        if (!visit[v]) {
            s += dfs(v) + 1;
        }
    }
    maxx[x] = max(s, n - 1 - s);
    return s;
}

int dfs2(int x, int deep) {
    visit[x] = 1;
    int cnt = 0;
    for (int i = head[x]; i; i = edge[i].next) {
        if (!visit[edge[i].v]) cnt += dfs2(edge[i].v, deep + 1);
    }
    return cnt + deep * 1;
}

int main() {
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        adde(a, b);
    }
    dfs(1);
    int ans = 0x7f7f7f7f, c = 0;
    for (int i = 1; i <= n; i++) {
        if (ans > maxx[i]) {
            ans = maxx[i], c = i;
        }
    }
    cout << c << " ";
    memset(visit, 0, sizeof(visit));
    cout << dfs2(c, 0) << endl;
}
2022/10/23 10:10
加载中...