WA on #4~5 #7~10

记录

code：

#include <bits/stdc++.h>
#define INF 0x3fffffff
#define INFF 1e18
#define endl '\n'
#define lson id << 1
#define rson id << 1 | 1
#define LL long long
#define ULL unsigned long long

using namespace std;

const int N = 5e5 + 5, M = 2e6 + 5;

int hd[N], cnt;
int u[M << 1], v[M << 1], w[N], n, m;
int dfn[N], low[N], times, st[N], top;
int tot, color[N], d[N];
int fa[N][25], lg[N], dep[N], c[N];

struct Edge {
	int to, nx;
} e[M << 1];

void add(int u, int v) {
	e[ ++ cnt] = {v, hd[u]}, hd[u] = cnt;
}

void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++ times, st[ ++ top] = u;
	for (int i = hd[u]; i; i = e[i].nx) {
		int v = e[i].to;
		if (!dfn[v]) {
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
		} else if (v != fa) low[u] = min(low[u], dfn[v]);
	}
	if (low[u] == dfn[u]) {
		tot ++;
		while (1) {
			int v = st[top -- ];
			color[v] = tot, d[tot] += w[v];
			if (v == u) break;
		}
	}
}

void dfs(int u, int fat) {
	dep[u] = dep[fat] + 1; fa[u][0] = fat;
	for (int i = 1; i <= lg[dep[u]]; i ++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for (int i = hd[u]; i; i = e[i].nx) {
		int v = e[i].to;
		if (v != fat) dfs(v, u);
	}
}

void init() {
	for (int i = 1; i <= tot; i ++) lg[i] = lg[i - 1] + ((1 << lg[i - 1]) == i);
	dfs(1, 0);
}

int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	while (dep[x] > dep[y]) x = fa[x][lg[dep[x] - dep[y]] - 1];
	if (x == y) return x;
	for (int i = lg[dep[x] - 1]; i >= 0; i --) {
		if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
	}
	return fa[x][0];
}

void solve(int u, int fa) {
	for (int i = hd[u]; i; i = e[i].nx) {
		int v = e[i].to;
		if (v == fa) continue;
		solve(v, u); c[u] += c[v];
	}
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);
	for (int i = 1; i <= m; i ++) { scanf("%d %d", &u[i], &v[i]); add(u[i], v[i]), add(v[i], u[i]); }
	tarjan(1, 0);
	for (int i = 1; i <= cnt; i ++) e[i] = {0, 0};
	for (int i = 1; i <= n; i ++) hd[i] = 0;
	cnt = 0;
	for (int i = 1; i <= m; i ++) {
		int x = color[u[i]], y = color[v[i]];
		if (x != y) add(x, y), add(y, x);
	}
	init();
	int q, ans = 0; cin >> q;
	while (q --) {
		int a, b; scanf("%d %d", &a, &b);
		int x = color[a], y = color[b]; int lca = LCA(x, y);
		c[x] ++, c[y] ++, c[lca] --, c[fa[lca][0]] --;
	}
	solve(color[1], 0);
	for (int i = 1; i <= tot; i ++) if (c[i] > 0) ans += d[i];
	cout << ans;
	return 0;
}

为了做这道题，复习了3个知识点，好评（