[BZOJ1040][[ZJOI2008]骑士][基环外向树+树形DP]

题目大意：

给定一个N<=1000000$N<= 1 000 000$个点的基环外向森林，求带权的最大独立集。

思路：

首先题目中看上去给出的是有向边但实际上是无向边，因为v$v$不会和u$u$在一起那么u$u$也不会和v$v$在一起。

这道题一开始我以为只是一棵普通的树，那这样直接树形dp$dp$就好了，用f[u][1],f[u][0]$f[u][1],f[u][0]$表示u$u$点选中或者不选的最大值，不妨设v$v$为u$u$的儿子，那么状态转移方程显然就是：

f[u][0]=∑Max(f[v][1],f[v][0]) $$f[u][0]=/sum Max(f[v][1],f[v][0])$$ f[u][1]=∑f[v][0] $$f[u][1]= /sum f[v][0]$$

再读题发现自己傻逼了，题目总共给出了N$N$个点N$N$条边，显然形成了一棵基环外向树，但这样其实还是很好搞，我们dfs$dfs$或者bfs$bfs$找到树中的环把环的两头断开，显然两头不能同时选因为它们是联通的，那么我们分别让其中一个选，另一个不选，或者两个都不选分别搞一下树形dp$dp$，然后在结果中取最大值就好了。

再打完发现自己又傻逼了，显然所有骑士并不一定会连在一起，肯定是只有一棵基环外向树，另外有或没有很多棵普通的树。但其实还是一样搞，在最外层枚举一下每个点有没有vis$vis$过就好了，然后把每棵树的贡献加入ans$ans$

断边可以直接把边设为false$false$，但边是双向边而前向星的存法只能一条边表示一个方向，但（两级反转）加边的时候是两个方向的边是同时加入的，所有一条边的编号是id$id$，另一条边的编号就是id⊕1$id /oplus1$，处理起来很方便。

代码：

完。

By g1n0st