[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