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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
#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