BZOJ2314

八中有N个房间和N-1双向通道，任意两个房间均可到达。

现在出了一件极BT的事，就是八中开始闹鬼了。

老大决定加强安保，现在如果在某个房间中放一个士兵,则这个房间以及所有与这个房间相连的房间都会被控制。

现在，老大想知道至少要多少士兵可以控制所有房间。以及有多少种不同的方案数。

我的代码：

#include<bits/stdc++.h>
using namespace std;
using ll=unsigned long long;
const ll mod=1032992941ull;
int n,dp1[500005][3];//0：自己有士兵，1：儿子有士兵，2：只有父亲有士兵（手机网络） 
ll dp2[500005][3];
vector<int>con[500005];

void dfs(int u,int fa){
	dp1[u][0]=1,dp2[u][0]=dp2[u][1]=dp2[u][2]=1ull,dp1[u][1]=500010;
	for(int v:con[u]){
		if(v==fa)continue;
		dfs(v,u);
		int mn=min({dp1[v][0],dp1[v][1],dp1[v][2]});
		dp1[u][0]+=mn,dp2[u][0]=dp2[u][0]*(((dp1[v][0]==mn)*dp2[v][0]+(dp1[v][1]==mn)*dp2[v][1]+(dp1[v][2]==mn)*dp2[v][2])%mod)%mod;
		int a=dp1[u][1]+dp1[v][0],b=dp1[u][1]+dp1[v][1],c=dp1[u][2]+dp1[v][0];
		mn=min({a,b,c});
		dp1[u][1]=mn,dp2[u][1]=((a==mn)*dp2[u][1]*dp2[v][0]%mod+(b==mn)*dp2[u][1]*dp2[v][1]%mod+(c==mn)*dp2[u][2]*dp2[v][0]%mod)%mod;
		dp1[u][2]+=dp1[v][1],(dp2[u][2]*=dp2[v][1])%=mod;
	}
	return ;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		con[u].push_back(v);
		con[v].push_back(u);
	}
	dfs(1,0);
	if(dp1[1][0]<dp1[1][1])printf("%d\n%llu",dp1[1][0],dp2[1][0]);
	else if(dp1[1][0]>dp1[1][1])printf("%d\n%llu",dp1[1][1],dp2[1][1]);
	else printf("%d\n%llu",dp1[1][0],(dp2[1][0]+dp2[1][1])%mod);
	return 0;
}