[洛谷]P2016 战略游戏（树形dp）

树形结构!!!

因为是一棵树,所以对于每个节点,我们都把它当成根节点处理→→树形dp!!!

注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。

定义状态f[u][0/1]表示u这个节点不放/放士兵

根据题意,如果当前节点不放置士兵,那么它的子节点必须全部放置士兵,因为要满足士兵可以看到所有的边,所以

                 f[u][0]+=f[son][1];

其中son是u的子节点

如果当前节点放置士兵,它的子节点选不选已经不重要了(因为树形dp自下而上,上面的节点不需要考虑),所以

                 f[u][1]+=min(f[son][0],f[son][1]);

ACcode:

#include<bits/stdc++.h>
using namespace std;
const int N=1500+10;
vector<int>v[N];
int n,x,k,id,fa[N],f[N][2],ans=1<<30;
void dfs(int u){
	f[u][1]=1;
	for(int i=0;i<v[u].size();i++){
		int son=v[u][i];
		dfs(son);
		f[u][1]+=min(f[son][0],f[son][1]);
		f[u][0]+=f[son][1];
	}
}
void solve() {
  cin>>n;
  for(int i=1;i<=n;i++){//建图 
  	cin>>id>>k;
  	while(k--){
  		cin>>x;
  		v[id].push_back(x);
  		fa[x]=true;
	  } 
  }
  for(int i=0;i<n;i++){
  	if(fa[i]==false){
  		memset(f,0,sizeof f);
  		dfs(i);
  		ans=min(ans,min(f[i][1],f[i][0]));
	  }
  }
  cout<<ans<<"\n";
}
int main() {
 
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	solve();
	return 0;
}

over~

另外思考：无根无向树的根节点怎么求