灵异事件

题意

同潜入行动「JSOI2018」，但是监听器会监听自己。

---

思路

本题除了维护最少数量还需要维护方案数量。

子状态(f[n][0/1/2])，表示(n)被自己、父亲或是儿子控制，(cnt[n][0/1/2])侧表示方案数量。

转移分类讨论：

(f[now][0]=min(f[to][0],f[to][1],f[to][2]))

(cnt[now][0]=被谁转移过来方案就乘以谁)

(f[now][1]=min(f[now[1]+min(f[to][0],f[to][1]),f[now][2]+f[to][0]))

(cnt[now][1]=被谁转移过来方案就乘以谁)

(f[now][2]+=f[to][1])

(cnt[now][2]*=cnt[to][1])

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

	template<typename T>inline void read (T &x) {
		x=0;T f=1;char c=getchar();
		for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
		for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
		x*=f;
	}

	template<typename T>inline void write (T x) {
		if (x<0) putchar('-'),x*=-1;
		if (x>=10) write(x/10);
		putchar(x%10+'0');
	}

}

using namespace StandardIO;

namespace Project {
	#define int long long
	
	const int N=500500;
	const int INF=0x3f3f3f3f;
	const int MOD=1032992941;
	
	int n;
	int top;
	int head[N];
	struct node {
		int to,next;
	} edge[N<<1];
	int dp[N][3],cnt[N][3],size[N];
	
	inline void add (int a,int b) {
		edge[++top].to=b,edge[top].next=head[a],head[a]=top;
	}
	void dfs (int now,int fa) {
		dp[now][0]=1,dp[now][1]=n,dp[now][2]=0;
		cnt[now][0]=cnt[now][1]=cnt[now][2]=1;
		for (register int i=head[now]; i; i=edge[i].next) {
			int to=edge[i].to;
			if (to==fa) continue;
			dfs(to,now);
			int val=min(dp[to][0],min(dp[to][1],dp[to][2])),tot=0;
			dp[now][0]=(dp[now][0]+val)%MOD;
			for (register int i=0; i<=2; ++i) if (dp[to][i]==val) tot=(tot+cnt[to][i])%MOD;
			cnt[now][0]=(cnt[now][0]*tot)%MOD;
			
			val=min(dp[now][1]+min(dp[to][0],dp[to][1]),dp[now][2]+dp[to][0]),tot=0;
			for (register int i=0; i<=1; ++i) if (dp[now][1]+dp[to][i]==val) tot=(tot+cnt[to][i])%MOD;
			cnt[now][1]=(cnt[now][1]*tot)%MOD;
			if (dp[now][2]+dp[to][0]==val) cnt[now][1]=(cnt[now][1]+cnt[now][2]*cnt[to][0]%MOD)%MOD;
			dp[now][1]=val%MOD;
			
			dp[now][2]=(dp[now][2]+dp[to][1])%MOD;
			cnt[now][2]=(cnt[now][2]*cnt[to][1])%MOD;
		}
	}

	inline void MAIN () {
		read(n);
		for (register int i=1; i<n; ++i) {
			int x,y;
			read(x),read(y);
			add(x,y),add(y,x);
		}
		dfs(1,1);
		int ans=min(dp[1][0],dp[1][1]),tot=0;
		for (register int i=0; i<=1; ++i) if (dp[1][i]==ans) tot=(tot+cnt[1][i])%MOD;
		write(ans),putchar('
'),write(tot);
	}
	
	#undef int
}

int main () {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	Project::MAIN();
}