Submission #225743

#TimeUsernameProblemLanguageResultExecution timeMemory
225743osaaateiasavtnlMag (COCI16_mag)C++14
120 / 120
653 ms252664 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define ii pair <int, int> #define app push_back #define all(a) a.begin(), a.end() #define bp __builtin_popcount #define ll long long #define mp make_pair #define f first #define s second #define Time (double)clock()/CLOCKS_PER_SEC const int N = 1e6 + 7, INF = 1e9 + 7; int n, a[N]; vector <int> g[N]; int x, y; void relax(int a, int b) { if (a * y < x * b) { x = a; y = b; } } int down[N]; void dfs1(int u, int p) { down[u] = a[u] == 1; for (int v : g[u]) { if (v != p) { dfs1(v, u); if (a[u] == 1) down[u] = max(down[u], down[v] + 1); } } } int up[N]; void dfs2(int u, int p) { vector <int> d = {0, 0}; for (int v : g[u]) { if (v != p) { d.app(down[v]); } } sort(all(d)); reverse(all(d)); for (int v : g[u]) { if (v != p) { if (a[u] != 1) { up[v] = 0; } else { int h = d[d[0] == down[v]]; up[v] = max(up[u], h) + 1; } dfs2(v, u); } } relax(a[u], d[0] + d[1] + 1); relax(a[u], up[u] + d[0] + 1); } signed main() { #ifdef HOME freopen("input.txt", "r", stdin); #else #define endl '\n' ios_base::sync_with_stdio(0); cin.tie(0); #endif cin >> n; for (int i = 0; i < n - 1; ++i) { int u, v; cin >> u >> v; g[u].app(v); g[v].app(u); } x = INF; y = 1; for (int i = 1; i <= n; ++i) { cin >> a[i]; relax(a[i], 1); } dfs1(1, 1); dfs2(1, 1); int t = __gcd(x, y); x /= t; y /= t; cout << x << '/' << y << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...