96分求调
查看原帖
96分求调
1281266
TimADE楼主2024/8/30 11:33
#include<bits/stdc++.h>
#define ll long long
#define INF 2147483647
inline int inp(){
    char c = getchar();
    while(c < '0' || c > '9')
        c = getchar();
    int sum = 0;
    while(c >= '0' && c <= '9'){
        sum = sum * 10 + c - '0';
        c = getchar();
    }
    return sum;
}
int head[100010];
int nxt[20010];
int end[20010];
char type[100000];
int num1[100000], num2[100000];
int cnt = 0;
int cou = 0;
int f[20010];
void link(int a, int b){
    nxt[++cou] = head[a];
    head[a] = cou;
    end[cou] = b;
}
void dfs(int cur, int last){
    int max = 0;
    bool mt = true;
    for(int x = head[cur]; x != -1; x = nxt[x]){
        if(end[x] != last){
            dfs(end[x], cur);
            if(f[end[x]] > max){
                max = f[end[x]];
                mt = false;
            } else if(f[end[x]] == max)
                mt = true;
        }
    }
    if(mt)
        f[cur] = max + 1;
    else
        f[cur] = max;
}
void dfs2(int cur, int last){
    int max = 0;
    bool mt = true;
    int degree = 0;
    int pos;
    for(int x = head[cur]; x != -1; x = nxt[x]){
        if(end[x] != last){
            dfs(end[x], cur);
            if(f[end[x]] > max){
                max = f[end[x]];
                mt = false;
                pos = end[x];
            } else if(f[end[x]] == max)
                mt = true;
            degree++;
        }
    }
    if(degree == 0){
        type[++cnt] = 'B';
        num1[cnt] = cur;
        return ;
    }
    for(int x = head[cur]; x != -1; x = nxt[x]){
        if(end[x] != pos && end[x] != last){
            type[++cnt] = 'L';
            num1[cnt] = cur;
            type[++cnt] = 'M';
            num1[cnt] = cur;
            num2[cnt] = end[x];
            dfs2(end[x], cur);
        }
    }
    type[++cnt] = 'M';
    num1[cnt] = cur;
    num2[cnt] = pos;
    dfs2(pos, cur);
    if(mt)
        f[cur] = max + 1;
    else
        f[cur] = max;
}
int main(){
    memset(head, -1, sizeof(head));
    int n = inp();
    for(int i = 1; i < n; i++){
        int u = inp();
        int v = inp();
        link(u, v);
        link(v, u);
    }
    int root = 0;
    int min = INF;
    for(int i = 1; i <= n; i++){
        dfs(i, 0);
        if(f[i] < min){
            min = f[i];
            root = i;
        }
    }
    dfs2(root, 0);
    printf("%d\n%d\n", min, cnt + 1);
    printf("L %d\n", root);
    for(int i = 1; i <= cnt; i++){
        putchar(type[i]);
        printf(" %d", num1[i]);
        if(type[i] == 'M')
            printf(" %d", num2[i]);
        putchar('\n');
    }
}
2024/8/30 11:33
加载中...