全RE求调
查看原帖
全RE求调
1219662
wwxxbb楼主2024/8/10 22:40
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 200010;

int n;

struct Edge {int to, ne, w1, w2;} e[N << 1];
int h[N], idx;
void add(int u, int v, int x, int y) {e[idx] = {v, h[u], x, y}, h[u] = idx ++;}

int dep[N], fa[N], siz[N], son[N], top[N];
void dfs1(int u, int f) {
	dep[u] = dep[f] + 1, fa[u] = f, siz[u] = 1;
	for (int i = h[u]; ~i; i = e[i].ne) {
		int v = e[i].to;
		if (v == f) continue;
		dfs1(v, u);
		siz[u] += siz[v];
		if (siz[son[u]] < siz[v])
			son[u] = v;
	}
}
void dfs2(int u, int t) {
	top[u] = t;
	if (!son[u]) return;
	dfs2(son[u], t);
	for (int i = h[u]; ~i; i = e[i].ne) {
		int v = e[i].to;
		if (v == son[u] || v == fa[u]) continue;
		dfs2(v, v);
	}
}

int lca(int u, int v) {
	while (top[u] ^ top[v])
		dep[top[u]] > dep[top[v]] ? u = fa[top[u]] : v = fa[top[v]];
	return dep[u] > dep[v] ? v : u;
}

ll g[N], ans;
void dfs(int u) {
	int x;
	for (int i = h[u]; ~i; i = e[i].ne) {
		int v = e[i].to;
		if (v == fa[u]) {x = i; continue;}
		dfs(v);
		g[u] += g[v];
	}
	ans += min(1ll * g[u] * e[x].w1, 1ll * e[x].w2);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	memset(h, -1, sizeof h);
	cin >> n;
	for (int i = 1, u, v, x, y; i < n; i ++) {
		cin >> u >> v >> x >> y;
		add(u, v, x, y), add(v, u, x, y);
	}
	dfs1(1, 0), dfs2(1, 1);
	for (int i = 1; i < n; i ++)
		g[i] ++, g[i + 1] ++, g[lca(i, i + 1)] -= 2;
	dfs(1);
	return cout << ans, 0;
}
2024/8/10 22:40
加载中...