9,10 tle 求助
查看原帖
9,10 tle 求助
448887
cancan123456楼主2022/11/15 21:04
#include <cstdio>
using namespace std;
const int N = 20005;
struct Edge {
	int v, w, next;
} edge[2 * N];
int head[N];
int cnt;
void add_edge(int u, int v, int w) {
	cnt++;
	edge[cnt].v = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt;
}
bool vis[N];
int size[N], center, max_size;
int max(int a, int b) {
	return a > b ? a : b;
}
void calc_size(int u, int fa, int cnt) {
	int now = 0;
	size[u] = 1;
	for (int v, i = head[u]; i != 0; i = edge[i].next) {
		v = edge[i].v;
		if (v != fa && !vis[v]) {
			calc_size(v, u, cnt);
			now = max(now, size[v]);
			size[u] += size[v];
		}
	}
	now = max(now, cnt - size[u]);
	if (now < max_size) {
		center = u;
	}
}
int num[3];
void get_dis(int u, int fa, int dis) {
	num[dis]++;
	for (int v, i = head[u]; i != 0; i = edge[i].next) {
		v = edge[i].v;
		if (v != fa && !vis[v]) {
			get_dis(v, u, (dis + edge[i].w) % 3);
		}
	}
}
int solve(int u, int w) {
	num[0] = num[1] = num[2] = 0;
	get_dis(u, 0, w);
	return num[0] * num[0] + 2 * num[1] * num[2];
}
int dfs(int u) {
	int ans = 0;
	vis[u] = true;
	ans += solve(u, 0);
	for (int v, i = head[u]; i != 0; i = edge[i].next) {
		v = edge[i].v;
		if (!vis[v]) {
			ans -= solve(v, edge[i].w);
			max_size = 0x7fffffff;
			calc_size(v, u, size[v]);
			ans += dfs(center);
		}
	}
	return ans;
}
int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}
int main() {
	int n;
	scanf("%d", &n);
	for (int u, v, w, i = 1; i < n; i++) {
		scanf("%d %d %d", &u, &v, &w);
		add_edge(u, v, w % 3);
		add_edge(v, u, w % 3);
	}
	max_size = 0x7fffffff;
	calc_size(1, 0, n);
	int ans = dfs(center);
	int g = gcd(ans, n * n);
	printf("%d/%d", ans / g, n * n / g);
	return 0;
}
2022/11/15 21:04
加载中...