Submission #44693925

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define x first
#define y second
#define mp(x, y) make_pair(x, y)
#define fro(i, x, y) for(int i = (x);i <= (y);i++)
#define pre(i, x, y) for(int i = (x);i >= (y);i--)

typedef long long ll;
typedef __int128 lll;
// typedef unsigned int uint;
typedef pair<int, int> PII;
typedef unsigned long long ull;

const int N = 1000010;
const int mod = 998244353;

int n, m, cnt, a[N], fa[N], head[N]; ll num, ans;
struct edge { int to, nxt; } e[N];
inline void add(int x, int y)
{
    e[++cnt] = {y, head[x]}, head[x] = cnt;
    e[++cnt] = {x, head[y]}, head[y] = cnt;
}
inline pair<ll, ll> dfs(int now, int fa)
{
    ll w = 0, h = 1; if(a[now]) h = 0, w += a[now] - 1;
    for(int i = head[now];i;i = e[i].nxt)
    {
        if(e[i].to == fa) continue;
        auto j = dfs(e[i].to, now);
        num += j.x + j.y, w += j.x, h += j.y;
    }
    ll x = min(w, h); w -= x, h -= x;
    if(now == 1 && (w || h)) num = -1;
    return mp(h, w);
}
inline int gf(int x)
{
    return (fa[x] == x ? x : fa[x] = gf(fa[x]));
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m; int vx = 0, vy = 0;
    iota(fa + 1, fa + n + 1, 1), ans = 1e17;
    fro(i, 1, m)
    {
        int x, y; cin >> x >> y;
        if(gf(x) == gf(y))
            vx = x, vy = y;
        else add(x, y), fa[gf(x)] = gf(y);
    }
    if(!vx && !vy)
        num = 0, dfs(1, 0), ans = num;
    else
    {
        auto x = dfs(1, 0);
        ans = min(ans, num);
        int flag = num;
        a[vx] = a[vy] = 1, num = 1;
        auto y = dfs(1, 0);
        if(num != -1) ans = min(ans, num);
        if(num != -1 && flag != -1 && num != flag)
        {
            int op = (flag > num ? 1 : -1), now = 0;
            for(int i = 28;i >= 0;i--)
            {
                now = now + (1 << i);
                a[vx] = a[vy] = op * now, num = now, dfs(1, 0); int f1 = num;
                a[vx] = a[vy] = op * (now + 1), num = (now + 1), dfs(1, 0); int f2 = num;
                if(f1 < f2) now = now - (1 << i);
            }
            a[vx] = a[vy] = op * now, num = now, dfs(1, 0);
            ans = min(ans, num);
            a[vx] = a[vy] = op * (now + 1), num = (now + 1), dfs(1, 0);
            ans = min(ans, num);
        }
        else if(x.x || x.y)
        {
            if(x.x && !y.y && x.x != y.x)
            {
                int g = x.x - y.x;
                if(x.x % g == 0)
                {
                    a[vx] = a[vy] = x.x / g;
                    num = abs(x.x / g), dfs(1, 0), ans = num;
                }
            }
            if(x.y && !y.x && x.y != y.y)
            {
                int g = x.y - y.y;
                if(x.y % g == 0)
                {
                    a[vx] = a[vy] = x.y / g;
                    num = abs(x.y / g), dfs(1, 0), ans = num;
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

Submission Info

Judge Result