Submission #1106242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106242		nh0902	Mag (COCI16_mag)	C++14	0 / 120	482 ms	205636 KiB

mag

#include <bits/stdc++.h>

using namespace std;

const int N = 1100000;

const long long inf = LLONG_MAX;

int n, pa[N];

long long X[N], P, Q, down[N], up[N];

vector<int> g[N];

long long pre_dfs(int u, int p) {
    long long l = 1;
    pa[u] = p;
    for (int v : g[u]) if (v != p) {
        l = max(l, pre_dfs(v, u) + 1);
    }

    if (X[u] > 1) {
        down[u] = 0;
    } else {
        down[u] = l;
    }
    //cout << u << " : " << down[u] << "\n";
    return down[u];
}

void BFS(int u, int p) {

    long long l1 = up[pa[u]];
    long long l2 = 0;
    for (int v : g[u]) if (v != p) {
        l2 = max(l2, down[v]);
        if (l2 > l1) swap(l1, l2);
    }

    long long new_P = X[u];
    long long new_Q = 1 + l1 + l2;
    cout << u << " : " << new_P << " , " << new_Q;
    if (new_P * Q < new_Q * P) {
        P = new_P;
        Q = new_Q;
    }

    if (X[u] > 1) up[u] = 0;
    else up[u] = up[pa[u]] + 1;
    cout << " , " << up[u] << "\n";
    for (int v : g[u]) if (v != p) {
        BFS(v, u);
    }
}

long long gcd(long long a, long long b) {
    long long r = b % a;
    if (r == 0) return a;
    return gcd(r, a);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;

    int a, b;
    for (int i = 1; i < n; i ++) {
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    bool has_1 = false;
    for (int i = 1; i <= n; i ++) {
        cin >> X[i];
        if (X[i] == 1) {
            has_1 = true;
        }
    }

    if (!has_1) {
        P = X[1];
        for (int i = 1; i <= n; i ++) {
            P = min(P, X[i]);
        }
        cout << P << "/" << "1";
        return 0;
    }

    P = 1;
    Q = 1;

    pre_dfs(1, 1);
    BFS(1, 1);

    long long d = gcd(P, Q);
    cout << P/d << "/" << Q/d;

    return 0;
}

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