先贴代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int n, rx, ry;
ll dp[1000001][2], p[1000001];
int fa[1000001], u[1000001];
bool vis[1000001];
int mark[2];

struct Edge
{
	int v, nxt;
}e[2000001];
int cnt = 0, head[1000001];

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

void DFS1(int cur)
{
	vis[cur] = 1;
	for (int i = head[cur]; i; i = e[i].nxt)
	{
		int it = e[i].v;
		if (it == fa[cur]) continue;
		if (vis[it]) 
		{
			rx = cur, ry = it;
			continue;
		}
		fa[it] = cur;
		DFS1(it);
	}
}

void DFS2(int cur)
{
	dp[cur][0] = 0;
	dp[cur][1] = p[cur];
	for (int i = head[cur]; i; i = e[i].nxt)
	{
		int it = e[i].v;
		if (it == fa[cur]) continue;
		if ((cur == ry && it == rx) || (cur == rx && it == ry)) continue;
		DFS2(it);
		dp[cur][1] += dp[it][0];
		dp[cur][0] += max(dp[it][0], dp[it][1]);
	}
	if (cur == rx && mark[0]) dp[cur][mark[0] - 1] = -1e15;
	else if (cur == ry && mark[1]) dp[cur][mark[1] - 1] = -1e15;
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> p[i] >> u[i];
		if (u[u[i]] != i) AddEdge(i, u[i]);
	}
	ll fans = 0;
	for (int i = 1; i <= n; i++)
	{
		if (!vis[i])
		{
			ll cura = 0;
			DFS1(i);
			mark[0] = 2, mark[1] = 1;
			DFS2(i);
			cura = max(cura, max(dp[i][0], dp[i][1]));
			mark[0] = 1, mark[1] = 2;
			DFS2(i);
			cura = max(cura, max(dp[i][0], dp[i][1]));
			mark[0] = 2, mark[1] = 2;
			DFS2(i);
			cura = max(cura, max(dp[i][0], dp[i][1]));
			fans += cura;
		}
	}
	cout << fans << endl;
	return 0;
}

思路是将不在 DFS 树上面的那一条边的两个端点强行定一个不选，另一个选或者两个都不选，每个连通块跑三遍 DP 取最大值。
请问为什么这种做法是正确的，以及为什么如果去掉两个都不选的情况时会 WA，另外，为什么以上代码用 vector 存图会 T 最后一个点。
评测记录：AC TLE