ZJOI 2008 骑士

​ 题意：https://www.luogu.com.cn/problem/P2607

---

​ 显然的图论题。我们把每个骑士看作一个点，将每个骑士与他厌恶的骑士连一条无向边。然后就会发现这题跟 没有上司的舞会（https://www.luogu.com.cn/problem/P1352） 有点类似。如果一个点选了，那么所有与它相连的点就不能选。但是，没有上司的舞会给出的图是一棵树。我们可以通过 树形dp 轻松解决这样的问题。而本题中则是有 \(n\) 条边，\(n\) 个点，每个点都与一条边相接。它并不是一颗树，它是另外一种特殊的图基环树。这种图点数与边数相同（但点数与边数相同的图不一定是基环树，基环树实际上是通过在一棵树上加一条边形成的），对于这种图我们不在赘述，可以自行百度。对于基环树，我们有一种常规的处理方法。对于每一个联通块来说，最多只会存在一个环。 因为对于一个环来说点数与边数是相同的，所以要将两个环直接相连就必定要再加一条边，而如果通过 \(x\) 个点连接，那么最少也还要 \(x+1\) 条边。无论哪种情况都不符合我们题目给出的图。

​ 知道每个联通快中最多存在一个环，那么我们可以通过拆去环中的一条边来将这个联通块变成一棵树。找环的任务我们可以通过并查集轻松解决。我们考虑在输入时对于 \(u\) 与 \(u\) 的仇人 \(v\) 。如果他们已经在一个集合当中，记录下这条边（此时不用再将两个点归并为一个集合，也不用连边，只需记录），否则，将两个点所在集合合并，同时连一条边。注意：图不一定是联通图，所以我们对每个联通块都要找边。也就是说我们可能记下多条边。

​ 然后我们对每条记录下的边进行操作（每条边就代表着每一个联通块），由于每一个联通块已经变成树了。我们进行 树形dp 并将答案进行累加就好。注意：\(u,v\) 是不能同时选用的，我们考虑设 \(dp_{i,0/1}\) 为以 \(i\) 为根的子树，是否选用 \(i\) 的战斗力的最大值（0表示不选，1表示选）。那么转移方程为（其中 \(j\) 表示 \(i\) 的儿子）：

\[\begin{aligned} dp_{i,0}&=dp_{i,0}+\max(dp_{j,1},dp_{j,0})\\ dp_{i,1}&=dp_{i,1}+dp_{j,0} \end{aligned} \]

​ 然后我们让最终答案 \(res\) 加上 \(\max(dp_{u,0},dp_{v,0})\) （这里的 \(u,v\) 表示记录下来的边的两个端点） 。

​ 总时间复杂度为：\(O(n+n\times \alpha(n))\)。其中 \(\alpha\) 为阿克曼函数的反函数，对于一个同时使用路径压缩和启发式合并的并查集来说，每个操作的平均时间为 \(O(\alpha(n))\)。（详见 oiwiki并查集部分）。我们把 \(\alpha(n)\) 看作一个常数就好了。

代码如下（代码中并没有用到启发式合并因为懒）：

#include<bits/stdc++.h>
#define ll long long
#define R register
using namespace std;
const int MAXN = 1e6+5;
int n,f[MAXN],head[MAXN],tot,edge[MAXN][2],cnt;
ll dp[MAXN][2],ans,v[MAXN];
bool flag;
int find(int x)
{
	return x==f[x]?x:f[x]=find(f[x]);
}
struct E
{
	int to,pre;
}e[MAXN<<1];
void add(int u,int v)
{
	e[++tot]=E{v,head[u]};
	head[u]=tot;
}
void dfs(int k,int fa)
{
	dp[k][0]=0,dp[k][1]=v[k];
	for(int i=head[k];i;i=e[i].pre)
	{
		int to=e[i].to;
		if(to==fa) continue;
		dfs(to,k);
		dp[k][0]=dp[k][0]+max(dp[to][0],dp[to][1]);
		dp[k][1]+=dp[to][0];
	}
}
int main()
{
	scanf("%d",&n);
	for(R int i=1;i<=n;++i) f[i]=i;
	for(R int i=1;i<=n;++i)
	{
		int x;
		scanf("%lld %d",&v[i],&x);
		if(find(i)==find(x))
		{
			++cnt;
			edge[cnt][0]=i;edge[cnt][1]=x;
			continue;
		}
		add(i,x);add(x,i);
		f[find(i)]=find(x);
	}
	ll ans=0,sum=0;
	for(R int i=1;i<=cnt;++i)
	{
		dfs(edge[i][0],0);ans=dp[edge[i][0]][0];
		dfs(edge[i][1],0);ans=max(ans,dp[edge[i][1]][0]);
		sum+=ans;
	}
	printf("%lld\n",sum);
	return 0;
}

​ 总结：基环树的题目大多的一种常规方法便是拆环，还是比较套路的一种方法，初见可能较难，还是刷的题不够。。。