首页 > 代码库 > 【vijos】1892 树上的最大匹配（树形dp+计数）
【vijos】1892 树上的最大匹配（树形dp+计数）
https://vijos.org/p/1892
这个必须得卡评测机+手动开栈才能卡过QAQ
手动开栈我百度的。。。
int size=256<<20; //256MBchar *p=(char*)malloc(size)+size;__asm__("movl %0, %%esp\n" :: "r"(p));然后我交了无数发，然后才卡过。。。。
我们设状态
f[i][0]表示i节点与儿子的边一个也不选
f[i][1]表示i节点只选一条与儿子的边
g[i][0]和g[i][1]对应方案
那么转移就是
f[i][0]=sigma{max{f[j][0], f[j][1]} j是i的儿子}
f[i][1]=max{f[j][0]+sigma{max{f[k][0], f[k][1]}} j和k都是i的儿子，j!=k }
方案的话同理
这样能做到不重不漏。。。
后者我们用前缀和和后缀和维护。。。
#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; }const int N=2000005;int ihead[N], cnt, n, f[N][2], st[N], r[N];ll MD, sumr[N], d[N][2];struct ED { int next, to; }e[N<<1];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 dp(int x, int fa) { int t0=0; ll s0=1; for(int i=ihead[x]; i; i=e[i].next) if(e[i].to!=fa) { int y=e[i].to; dp(y, x); int mx=max(f[y][0], f[y][1]); ll tp=0; if(f[y][0]==mx) tp+=d[y][0]; if(f[y][1]==mx) tp+=d[y][1]; s0=(s0*tp)%MD; t0+=mx; } f[x][0]=t0; d[x][0]=s0; int sz=0, l=0; ll suml=1; for(int i=ihead[x]; i; i=e[i].next) if(e[i].to!=fa) st[++sz]=e[i].to; sumr[sz+1]=1; r[sz+1]=0; for3(i, sz, 1) { int mx=max(f[st[i]][0], f[st[i]][1]); ll tp=0; if(mx==f[st[i]][0]) tp+=d[st[i]][0]; if(mx==f[st[i]][1]) tp+=d[st[i]][1]; r[i]=r[i+1]+mx; sumr[i]=(sumr[i+1]*tp)%MD; } f[x][1]=-N; for1(i, 1, sz) { int tp=l+f[st[i]][0]+r[i+1]+1; if(tp>f[x][1]) { f[x][1]=tp; d[x][1]=(d[st[i]][0]*((suml*sumr[i+1])%MD))%MD; } else if(tp==f[x][1]) { d[x][1]=d[x][1]+(d[st[i]][0]*((suml*sumr[i+1])%MD))%MD; } int mx=max(f[st[i]][0], f[st[i]][1]); s0=0; if(mx==f[st[i]][0]) s0+=d[st[i]][0]; if(mx==f[st[i]][1]) s0+=d[st[i]][1]; suml=(suml*s0)%MD; l+=mx; }}int main() { int size=256<<20; char *p=(char*)malloc(size)+size; __asm__("movl %0, %%esp\n" :: "r"(p)); read(n); for1(i, 1, n-1) add(getint(), getint()); read(MD); int root=(n+1)>>1; dp(root, -1); int ans1=max(f[root][0], f[root][1]); ll ans2=0; if(ans1==f[root][0]) ans2+=d[root][0]; if(ans1==f[root][1]) ans2+=d[root][1]; printf("%d\n%lld\n", ans1, ans2%MD); return 0;}然后就行了。。
描述
doc 的学姐曾经也是一名 oier, 她有的时候会询问 doc 各种有趣的竞赛问题
虽然很简单, 但是对于 doc 来说都是曾经很美好的回忆
今天, 学姐不想出去逛街, 因为她看到了一道题目并为此发愁在.
树上的最大匹配是多少? 最大匹配解的方案共有多少组?
(首先树可以被看作是一个无向图G.
(对于无向图G来说, 其上的最大匹配是边集的一个子集, 满足:
(对于G中每一个点来说, 都只有最多一条与之相连的边在这个子集中.
(最大匹配就是这个子集大小可以到达的最大值.
格式
输入格式
第一行输入一个整数 n, 表示树上的结点个数. 所有结点依次编号为 1 到 n.
之后 n-1 行, 每行有两个整数 a , b 表示有一条链接结点 a 和 b的边.
最后一行有一个整数 m, 表明对于最大匹配解的方案, 我们只需要输出对 m 取的余数.
输出格式
第一行有一个整数, 表示最大匹配有多大.
第二行有一个整数, 表示对 m 取余后的方案总数.
样例1
样例输入1[复制]
51 23 24 51 417
样例输出1[复制]
23
限制
对于30%的数据, n<=2500.
对于70%的数据, n<=100,000.
对于100%的数据, n<=1,500,000.
m为32位有符号整数
【vijos】1892 树上的最大匹配（树形dp+计数）