BZOJ1040 [ZJOI2008]骑士

多少年前的坑了。

用mac写的第一篇题解呢。

环套树DP。先把树上的情况处理了，然后枚举取不取环上的第一个。

要注意会有重边的情况，比较恶心。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>

using namespace std;

const int buf_len = 4000;
char buf[buf_len], *bufb(buf), *bufe(buf + 1);
#define readBuf() { \
	if (++ bufb == bufe) \
		bufe = (bufb = buf) + fread(buf, 1, sizeof(buf), stdin); \
}
#define readInt(_x_) { \
	register int _s_(0); \
	do { \
		readBuf(); \
	} while (!isdigit(*bufb)); \
	do { \
		_s_ = _s_ * 10 + *bufb - 48; \
		readBuf(); \
	} while (isdigit(*bufb)); \
	_x_ = _s_; \
}

typedef long long dint;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif

struct edge {
	int t;
	edge *next;
};

const int maxn = 1000009;

int n, v[maxn];
int stc[maxn], tst, lpp[maxn], tlp;
int vis[maxn], onl[maxn];
dint f[maxn], g[maxn];
edge elst[maxn << 1], *ep(elst), *head[maxn];

inline void addEdge(int u, int v) {
	ep-> t = v;
	ep-> next = head[u];
	head[u] = ep ++;
}

void dfsLoop(int p, int fr) {
	vis[p] = fr + 1;
	stc[tst ++] = p;
	for (edge* e = head[p]; e; e = e-> next)
		if (e-> t != fr) {
			if (!vis[e-> t]) {
				dfsLoop(e-> t, p);
			}
			else if (vis[e-> t] && vis[e-> t] != p + 1) {
				if (onl[p])
					continue;
				tlp = 0;
				do {
					-- tst;
					lpp[tlp ++] = stc[tst];
					onl[stc[tst]] = 1;
				} while (stc[tst] != e-> t);
			}
		}
	if (stc[tst - 1] == p)
		-- tst;
}

void dfsDP(int p, int fr) {
	f[p] = 0;
	g[p] = v[p];
	vis[p] = -1;
	for (edge* e = head[p]; e; e = e-> next)
		if (e-> t != fr && !onl[e-> t] && vis[e-> t] != -1) {
			dfsDP(e-> t, p);
			f[p] += max(f[e-> t], g[e-> t]);
			g[p] += f[e-> t];
		}
}

dint calcCC(int p) {
	tst = 0;
	tlp = 0;
	dfsLoop(p, 0);
	if (!tlp)
		lpp[tlp ++] = p;
	for (int i = 0; i < tlp; ++ i)
		dfsDP(lpp[i], 0);
	dint s0(0), s1(0);
	if (tlp < 3) {
		for (int i = 0; i < tlp; ++ i)
			s0 = max(s0, g[lpp[i]] - f[lpp[i]]);
		for (int i = 0; i < tlp; ++ i)
			s0 += f[lpp[i]];
	}
	else {
		dint f0(g[lpp[0]] + f[lpp[1]] + f[lpp[tlp - 1]]), g0(f0);
		for (int i = 2; i < tlp - 1; ++ i) {
			dint f1(f[lpp[i]] + max(f0, g0)), g1(g[lpp[i]] + f0);
			f0 = f1;
			g0 = g1;
		}
		s0 = max(f0, g0);
	}
	if (tlp < 3) {
		s1 = s0;
	}
	else {
		dint f0(f[lpp[0]]), g0(f0);
		for (int i = 1; i < tlp; ++ i) {
			dint f1(f[lpp[i]] + max(f0, g0)), g1(g[lpp[i]] + f0);
			f0 = f1;
			g0 = g1;
		}
		s1 = max(g0, f0);
	}
	return max(s0, s1);
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	readInt(n);
	memset(head, 0, sizeof(head));
	for (int i = 1; i <= n; ++ i) {
		int x;
		readInt(v[i]);
		readInt(x);
		addEdge(i, x);
		addEdge(x, i);
	}
	memset(vis, 0, sizeof(vis));
	memset(onl, 0, sizeof(onl));
	dint ans(0);
	for (int i = 1; i <= n; ++ i)
		if (!vis[i])
			ans += calcCC(i);
	printf(lld "\n", ans);
}