首页 > 代码库 > 【vijos】1770 大内密探（树形dp+计数）
【vijos】1770 大内密探（树形dp+计数）
https://vijos.org/p/1770
不重不漏地设计状态才能正确的计数QAQ
虽然可能最优化是正确的，但是不能保证状态不相交就是作死。。。。
之前设的状态错了。。。
应该设
f[i][0]表示i点不取且至少有一个儿子取，且保证i点被覆盖
f[i][1]表示i点取儿子任意，且保证i点被覆盖
f[i][2]表示i点不取且i点的儿子也不取，保证i点不被覆盖！（即留给父亲覆盖）
f[i][2]表示i点不取且儿子也不取。并不是表示i点不取儿子任意！！！！！！！！！！要不然这样会出现交的情况！假设使用后者，那么就会产生和f[i][0]一样的状态！！！！！！
然后我们分别计数
g[i][0]表示f[i][0]的方案数，g[i][1]表示f[i][1]的方案数，g[i][2]表示f[i][2]的方案数，那么有初始化
g[i][0]=0 当i没有儿子时
而转移f[i][1]和f[i][2]很简单，即
f[i][1]=sigma{ min{f[j][0], f[j][1], f[j][2]} (j是i儿子) }
f[i][2]=sigma{ f[j][0] (j是i儿子) }
方案的话加法乘法原理上。。。
f[i][0]转移非常麻烦（因为还要顾及到g[i][0]，要做到不重不漏！）
首先我们知道，至少要有一个儿子选中状态才能转移。
如果不小心，很容易得到
f[i][0]=min{f[j][1]+sigma{min{f[k][0], f[k][1]}} (j和k均为i儿子且j!=k) }
这样虽然可以用技巧实现O(n)转移，但是方案却不能够得到！
比如i有2和3这两个儿子，f[3][0]=5, f[3][1]=3, f[2][0]=6, f[2][1]=3;那么转移的时候，两次决策都是f[2][1]+f[3][1]或f[3][1]+f[2][1]！！！！！这样显然不能计数。。重合了。。
所以我之前就这样sb了。。
那么我们考虑如何去重？我们分析得到，我们枚举要取的儿子时，之前枚举过的全部给取f[k][0]，没有取过的任意！！！！这样就不会重！
那么问题就好解决了，我们在枚举儿子时，维护一个前缀和f[k][0]，k是已经枚举过的，然后再维护一个后缀和，表示sum{min{f[l][0], f[l][1]}}，l是未枚举过的
计数的方法相同，那么问题就解决了orz
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;#define pii pair<int, int>#define mkpii make_pair<int, int>#define pdi pair<double, int>#define mkpdi make_pair<double, int>#define pli pair<ll, int>#define mkpli make_pair<ll, int>#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)#define printarr2(a, b, c) for1(_, 1, b) { rep(__, c) cout << a[_][__] << ‘\t‘; cout << endl; }#define printarr1(a, b) for1(_, 1, b) cout << a[_] << ‘\t‘; cout << endlinline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a<b?a:b; }#define rdm(x,i) for(int i=ihead[x]; i; i=e[i].next)const int N=100005, oo=~0u>>1, MD=1000000007;int ihead[N], cnt, n, f[N][3], l, r[N], st[N];ll d[N][3], suml, sumr[N];struct ED { int to, next; }e[N<<1];ll mul(ll a, ll b) { return ((a%MD)*(b%MD))%MD;}ll Plus(ll a, ll b) { return ((a%MD)+(b%MD))%MD;}void add(int u, int v) { e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v; e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].to=u;}void dfs(int x, int fa) { int t1=1, t2=0, s1=1, s2=1, y; rdm(x, i) if((y=e[i].to)!=fa) { ll tp=0; dfs(y, x); int mn=min(min(f[y][0], f[y][1]), f[y][2]); if(f[y][0]==mn) tp+=d[y][0]; if(f[y][1]==mn) tp+=d[y][1]; if(f[y][2]==mn) tp+=d[y][2]; s1=mul(s1, tp); tp=0; s2=mul(s2, d[y][0]); t1+=mn; t2+=f[y][0]; } f[x][1]=t1; f[x][2]=t2; d[x][1]=s1; d[x][2]=s2; int sz=0; rdm(x, i) if(e[i].to!=fa) st[++sz]=e[i].to; r[sz+1]=0; sumr[sz+1]=1; suml=1; l=0; for3(i, sz, 1) { y=st[i]; int mn=min(f[y][0], f[y][1]); ll tp=0; if(f[y][0]==mn) tp+=d[y][0]; if(f[y][1]==mn) tp+=d[y][1]; r[i]=r[i+1]+mn; sumr[i]=mul(sumr[i+1], tp); } f[x][0]=N; for1(i, 1, sz) { if(l+f[st[i]][1]+r[i+1]<f[x][0]) { f[x][0]=l+f[st[i]][1]+r[i+1]; d[x][0]=mul(d[st[i]][1], mul(suml, sumr[i+1])); } else if(l+f[st[i]][1]+r[i+1]==f[x][0]) { d[x][0]=Plus(d[x][0], mul(d[st[i]][1], mul(suml, sumr[i+1]))); } if(f[st[i]][0]==N) break; l+=f[st[i]][0]; suml=mul(suml, d[st[i]][0]); }}int main() { read(n); for1(i, 1, n-1) add(getint(), getint()); int root=1; dfs(root, -1); int ans1=min(f[root][1], f[root][0]), ans2=0; if(ans1==f[root][0]) ans2=Plus(ans2, d[root][0]); if(ans1==f[root][1]) ans2=Plus(ans2, d[root][1]); printf("%d\n%d\n", ans1, ans2); return 0;}
背景
大内密探，负责秘密保护皇上，还有保护皇宫内外一切产业。——大内密探零零七
描述
在古老的皇宫中，有N个房间以及N-1条双向通道，每条通道连接着两个不同的房间，所有的房间都能互相到达。皇宫中有许多的宝物，所以需要若干个大内密探来守护。一个房间被守护当切仅当该房间内有一名大内密探或者与该房间直接相邻的房间内有大内密探。
现在身为大内密探零零七的你想知道要把整个皇宫守护好至少需要多少名大内密探以及有多少种安排密探的方案。两种方案不同当且仅当某个房间在一种方案有密探而在另一个方案内没有密探。
格式
输入格式
第一行一个正整数N.(1<=N<=100000)
后面N-1行，每行两个正整数a和b,表示房间a和房间b之间有一条无向通道。
房间的编号从1到N
输出格式
第一行输出正整数K，表示最少安排的大内密探。
第二行输出整数S,表示有多少种方案安排最少的密探，由于结果可能较大，请输出方案数mod 1000000007的余数。
样例1
样例输入1[复制]
72 13 14 25 16 27 6
样例输出1[复制]
34
限制
每个测试点1s
提示
30%保证:n <= 10
70%保证:n <= 1000
100%保证:n <= 100000
【vijos】1770 大内密探（树形dp+计数）