传送门

圆方树预备知识。

首先搞出DFS树，然后设状态$f[node][OK][OKanc]$为别表示在当前点选/不限和环顶节点选/不选。

剩下的就是TreeDP常规的东西。

P.S.课件上说第一个状态设为父亲的，亲测没有设成自己来得方便

//BZOJ 4316//by Cydiater//2017.2.12#include <iostream>#include <queue>#include <map>#include <ctime>#include <cstdlib>#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <iomanip>#include <cmath>#include <bitset>#include <set>#include <vector>using namespace std;#define ll long long#define up(i,j,n)	for(int i=j;i<=n;i++)#define down(i,j,n)	for(int i=j;i>=n;i--)#define cmax(a,b)	a=max(a,b)#define cmin(a,b)	a=min(a,b)#define Auto(i,node)	for(int i=LINK[node];i;i=e[i].next)const int MAXN=2e5+5;const int oo=0x3f3f3f3f;inline int read(){	char ch=getchar();int x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}int LINK[MAXN],N,M,len=0,fa[MAXN],dep[MAXN],anc[MAXN],f[MAXN][2][2],fat[MAXN];bool istop[MAXN];struct edge{	int y,next;}e[MAXN];namespace solution{	inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;}	inline void Insert(int x,int y){insert(x,y);insert(y,x);}	void DFS(int node,int father,int deep){		dep[node]=deep+1;fa[node]=father;		Auto(i,node)if(e[i].y!=father&&!dep[e[i].y])			DFS(e[i].y,node,deep+1);	}	void Prepare(){		N=read();M=read();		up(i,1,M){			int x=read(),y=read();			Insert(x,y);		}		DFS(1,0,0);		up(node,1,N)Auto(i,node){			if(dep[e[i].y]<dep[node]&&e[i].y!=fa[node]){				istop[e[i].y]=1;				anc[node]=e[i].y;				int tmp=node;				while(tmp!=e[i].y){					fat[tmp]=e[i].y;					tmp=fa[tmp];				}			}		}	}	int TreeDP(int node,int OK,int OKanc){		if(f[node][OK][OKanc]!=-1)return f[node][OK][OKanc];		f[node][OK][OKanc]=0;		if(OK){			if(anc[node]&&OKanc)return f[node][OK][OKanc];			Auto(i,node)if(dep[e[i].y]==dep[node]+1){				if(fat[e[i].y]==node&&istop[node])					f[node][OK][OKanc]+=TreeDP(e[i].y,0,1);				else f[node][OK][OKanc]+=TreeDP(e[i].y,0,OKanc);			}			f[node][OK][OKanc]++;		}else{			Auto(i,node)if(dep[e[i].y]==dep[node]+1){				if(fat[e[i].y]==node&&istop[node]){					f[node][OK][OKanc]+=max(TreeDP(e[i].y,0,0),TreeDP(e[i].y,1,0));				}				else f[node][OK][OKanc]+=max(TreeDP(e[i].y,0,OKanc),TreeDP(e[i].y,1,OKanc));			}					}		return f[node][OK][OKanc];	}}int main(){	//freopen("input.in","r",stdin);	using namespace solution;	Prepare();	memset(f,-1,sizeof(f));	cout<<max(TreeDP(1,1,1),TreeDP(1,0,0))<<endl;	return 0;}

BZOJ4316: 小C的独立集