Editorial for Trọng số ở đỉnh


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

#include <bits/stdc++.h>

using namespace std;

struct fraction {
    int nume, deno;

    fraction() {}
    fraction(int _nume, int _deno) {
        nume = _nume, deno = _deno;
    }

    fraction getFraction() {
        int g = __gcd(nume, deno);
        return fraction(nume / g, deno / g);
    }
};

int n, cnt, diameter, node1, node2;
vector <bool> vecVisit;
vector <int> vecV, vecVertice, vecId, vecDist;
vector <vector <int>> vecAdj;

void Task() {
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    if (fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
}

bool operator < (fraction fa, fraction fb) {
    return 1.0 * fa.nume / fa.deno < 1.0 * fb.nume / fb.deno;
}

void DFS1(int u, int id) {
    vecVisit[u] = true;
    cnt++;
    vecVertice.push_back(u);
    for (auto v : vecAdj[u]) {
        if (vecVisit[v]) continue;
        DFS1(v, id);
    }
}

void DFS2(int u, int d, int par, int id) {
    if (d > diameter) {
        diameter = d;
        node1 = u;
    }
    vecDist[u] = max(vecDist[u], d);
    for (auto v : vecAdj[u]) {
        if (v == par || vecId[v] != id) continue;
        DFS2(v, d + 1, u, id);
    }
}

int Diameter(int id, int u) {
    diameter = 0;
    DFS2(u, 1, - 1, id);
    node2 = node1;
    DFS2(node2, 1, - 1, id);
    DFS2(node1, 1, - 1, id);
    return diameter;
}

void Solve() {
    cin >> n;
    vecV.resize(n), vecAdj.resize(n);
    vector <vector <int>> vecEdge(n);
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        vecEdge[a].push_back(b);
        vecEdge[b].push_back(a);
    }
    int minv = 1e9;
    for (int i = 0; i < n; ++i) {
        cin >> vecV[i];
        minv = min(minv, vecV[i]);
    }
    if (minv != 1) {
        return void(cout << minv << "/1");
    }
    for (int i = 0; i < n; ++i) {
        if (vecV[i] != 1) continue;
        for (auto j : vecEdge[i]) {
            if (vecV[j] != 1) continue;
            vecAdj[i].push_back(j);
        }
    }
    vecVisit.assign(n, false), vecDist.assign(n, 1);
    vecId.resize(n);
    int maxx = 0, id = - 1;
    for (int i = 0; i < n; ++i) {
        if (vecV[i] != 1 || vecVisit[i]) continue;
        vecVertice.clear();
        cnt = 0;
        DFS1(i, ++id);
        for (auto j : vecVertice) {
            vecId[j] = id;
        }
        maxx = max(maxx, Diameter(id, i));
    }
    fraction ans = fraction(1, maxx);
    for (int i = 0; i < n; ++i) {
        if (vecV[i] == 1) continue;
        int max1 = 0, max2 = 0;
        for (auto j : vecEdge[i]) {
            if (vecV[j] != 1) continue;
            if (vecDist[j] >= max1) {
                max2 = max1;
                max1 = vecDist[j];
            } else if (vecDist[j] > max2) {
                max2 = vecDist[j];
            }
        }
        ans = min(ans, fraction(vecV[i], max1 + max2 + 1));
    }
    ans = ans.getFraction();
    cout << ans.nume << "/" << ans.deno;
}

int main() {
    Task();
    Solve();
}

Comments