80 pts WA求助
查看原帖
80 pts WA求助
688783
SilverLi楼主2023/6/11 23:18
#include <iostream>
#include <vector>
using namespace std;
#define min(a, b) (a < b ? a : b)
const int N = 1e6 + 5;
int n, a[N];
int p, q;
int m1[N], m2[N];
vector<int> g[N];
inline void ans(int P, int Q) {
	if (p * Q > P * q)
		p = P, q = Q;
}
void dfs(int u, int fa) {
	int f1, f2, g1, g2;
	f1 = f2 = g1 = g2 = 0;
	for (int i : g[u])
		if (i != fa) {
			dfs(i, u);
			if (m1[i] > m1[f1]) {
				f2 = f1;
				f1 = i;
			}
			else if (m1[i] > m1[f2])
				f2 = i;
			if (m2[i] > m2[g1]) {
				g2 = g1;
				g1 = i;
			}
			else if (m2[i] > m2[g2])
				g2 = i;
		}
	if (a[u] == 1) {
		ans(1, m1[f1] + m1[f2] + 1);
		m1[u] = m1[f1] + 1;
		if (g1 > 0) {
			m2[u] = m2[g1] + 1;
			if (f1 != g1 && f1 > 0)
				ans(2, m1[f1] + m2[g1] + 1);
			if (f2 != g1 && f2 > 0)
				ans(2, m1[f2] + m2[g1] + 1);
		}
		if (g2 > 0) {
			m2[u] = max(m2[u], m2[g2] + 1);
			if (f1 != g2 && f1 > 0)
				ans(2, m1[f1] + m2[g2] + 1);
			if (f2 != g2 && f2 > 0)
				ans(2, m1[f2] + m2[g2] + 1);
		}
	}
	if (a[u] == 2) {
		ans(2, m1[f1] + m1[f2] + 1);
		m2[u] = m1[f1] + 1;
	}
}
signed main() {
	cin >> n;
	for (int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int mx = 1e9;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		mx = min(mx, a[i]);
	}
	if (mx > 1) {
		cout << mx << '/' << 1;
		return 0;
	}
	p = 1e9;
	q = 1;
	dfs(1, 0);
	cout << p << '/' << q;
	return 0;
}

2023/6/11 23:18
加载中...