Submission #246189

#	Time	Username	Problem	Language	Result	Execution time	Memory
246189		NONAME	Mag (COCI16_mag)	C++14	120 / 120	510 ms	150684 KiB

mag

#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e6 + 100;

ll a[N], ap, aq, mx[N], mx1[N], mx2[N];
int n;
vector <int> g[N];

bool smaller(ll x, ll y) { return (x * aq) < (y * ap); }

void dfs(int v, int pr) {
    for (int u : g[v]) {
        if (u == pr)
            continue;
        dfs(u, v);

        if (mx[u] > mx1[v]) swap(mx1[v], mx2[v]), mx1[v] = mx[u];
            else if (mx[u] > mx2[v]) mx2[v] = mx[u];
    }

    if (a[v] == 1) mx[v] = mx1[v] + 1;
        else mx[v] = 0;
}

void dfs(int v, int pr, ll cur) {
    for (int u : g[v]) {
        if (u == pr)
            continue;
        ll cr = 0;

        if (a[v] == 1) {
            if (mx[u] == mx1[v]) cr = max(cur + 1, mx2[v] + 1);
                else cr = max(cur + 1, mx1[v] + 1);
        }

        dfs(u, v, cr);
    }

    ll a1 = mx1[v], a2 = mx2[v];

    if (cur > a1) swap(a1, a2), a1 = cur;
        else if (cur > a2) a2 = cur;

    if (smaller(a[v], a1 + a2 + 1)) {
        ap = a[v];
        aq = a1 + a2 + 1;
    }
}

int main() {
    fast_io;

    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int v, u;
        cin >> v >> u;
        --v, --u;

        g[v].push_back(u);
        g[u].push_back(v);
    }

    for (int i = 0; i < n; ++i)
        cin >> a[i];

    if (*min_element(a, a + n) > 1)
        return void(cout << *min_element(a, a + n) << "/1\n"), 0;

    ap = aq = 1;

    dfs(0, 0);
    dfs(0, 0, 0);

    ll gc = __gcd(ap, aq);

    cout << ap / gc << "/" << aq / gc << "\n";
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12