HDU 5452 Minimum Cut

本来以为是一道好题……

没想到xjb被我水过去了……

题目看不大懂去找题解看题意，都说什么LCA，醉了……真的不喜欢数据弱的题目。

题意：
给你一棵生成树，再多给你几条边，要你只能删除一条生成树的边的同时，最少删掉多少条边才能使得整张图图不联通。

思路：
一个很显然的规律就是，找到生成树上度数为1的点，再比较其他度数和即可……

这里有个漏洞，就是可以在删掉一条生成树上的边就可以分割整张图，简单说，就是桥……

不是很懂他们LCA的思路，水过了就不想思考了。我倒是觉得，直接tarjan缩点预处理一下，再特判一下缩点后的点数即可。

AC Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int maxn = 2e4 + 5;
const int maxm = 2e5 + 5;
const int inf = 0x3f3f3f3f;

int tree_degree[maxn];
int degree[maxn];
int n, m;

int main()
{
    int T, u, v;
    scanf("%d", &T);
    each(cas, T)
    {
        scanf("%d %d", &n, &m);
        fill(tree_degree, 0), fill(degree, 0);
        int ans = inf;
        each(i, n - 1) scanf("%d %d", &u, &v), tree_degree[u]++, tree_degree[v]++;
        each(i, m - n + 1) scanf("%d %d", &u, &v), degree[u]++, degree[v]++;
        range(i, 1, n) if (tree_degree[i] == 1) ans = min(ans, 1 + degree[i]);
        printf("Case #%d: %d\n", cas + 1, ans);
    }
    return 0;
}