fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8.  
  9. struct Fraction {
  10.     ll p, q;
  11.     bool operator<(const Fraction& other) const {
  12.         return (__int128)p * other.q < (__int128)other.p * q;
  13.     }
  14. };
  15.  
  16. const int MAXN = 1000005;
  17. vector<int> adj[MAXN];
  18. int x[MAXN];
  19. int f[MAXN]; // f[u] là độ dài chuỗi số 1 dài nhất kết thúc tại u (đi xuống lá)
  20. Fraction best = {2000000000, 1};
  21.  
  22. void dfs1(int u, int p) {
  23.     f[u] = (x[u] == 1 ? 1 : 0);
  24.     int max_f = 0;
  25.     for (int v : adj[u]) {
  26.         if (v == p) continue;
  27.         dfs1(v, u);
  28.         if (x[u] == 1) max_f = max(max_f, f[v]);
  29.     }
  30.     f[u] += max_f;
  31. }
  32.  
  33. void dfs2(int u, int p, int top_len) {
  34.     // Xét trường hợp đỉnh u là trung tâm của đường đi
  35.     vector<int> lens;
  36.     if (top_len > 0) lens.push_back(top_len);
  37.     for (int v : adj[u]) {
  38.         if (v != p && f[v] > 0) lens.push_back(f[v]);
  39.     }
  40.     sort(lens.rbegin(), lens.rend());
  41.  
  42.     // Cập nhật kết quả cho đỉnh u
  43.     if (x[u] == 1) {
  44.         int L = 1;
  45.         if (lens.size() >= 1) L += lens[0];
  46.         if (lens.size() >= 2) L += lens[1];
  47.         Fraction cur = {1, L};
  48.         if (cur < best) best = cur;
  49.     } else {
  50.         int L = 1;
  51.         if (lens.size() >= 1) L += lens[0];
  52.         if (lens.size() >= 2) L += lens[1];
  53.         Fraction cur = {(ll)x[u], L};
  54.         if (cur < best) best = cur;
  55.     }
  56.  
  57.     // Truyền dữ liệu xuống con
  58.     for (int v : adj[u]) {
  59.         if (v == p) continue;
  60.         int next_top = 0;
  61.         if (x[u] == 1) {
  62.             if (lens.size() >= 1 && f[v] == lens[0])
  63.                 next_top = (lens.size() >= 2 ? lens[1] : 0) + 1;
  64.             else
  65.                 next_top = (lens.size() >= 1 ? lens[0] : 0) + 1;
  66.         }
  67.         dfs2(v, u, next_top);
  68.     }
  69. }
  70.  
  71. int main() {
  72.     ios_base::sync_with_stdio(false);
  73.     cin.tie(NULL);
  74.  
  75.     int n; cin >> n;
  76.     for (int i = 0; i < n - 1; ++i) {
  77.         int u, v; cin >> u >> v;
  78.         adj[u].push_back(v); adj[v].push_back(u);
  79.     }
  80.     for (int i = 1; i <= n; ++i) {
  81.         cin >> x[i];
  82.         if (Fraction{x[i], 1} < best) best = {x[i], 1};
  83.     }
  84.  
  85.     dfs1(1, 0);
  86.     dfs2(1, 0, 0);
  87.  
  88.     ll g = __gcd(best.p, best.q);
  89.     cout << best.p / g << "/" << best.q / g << endl;
  90.  
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0.01s 29796KB
comments (?)
stdin
copy 
5
1 2
2 4
1 3
5 2
2
1
1
1
3
stdout
copy 
1/2
https://ideone.com/xGznGj
language:
C++ (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!