首页 > 代码库 > [vijos1892]树上的最大匹配(树形DP)

[vijos1892]树上的最大匹配(树形DP)

题目:https://vijos.org/p/1892

分析:(100分其实用到各种c++优化,没什么实际意义,所以弄70就可以了)

题目很简单,很容易想出用树形DP,但是求方案数的时候,满满都是细节……,本渣考试时候就跪了……只能膜拜神犇代码……

 1 #include <cstdio> 2 #include <cstring> 3 //#include <algorithm> 4  5 using namespace std; 6  7 typedef long long LL; 8  9 const int MaxN = 1500010;10 11 struct Node{12     int v;13     Node *nxt;14 }pool[MaxN << 1],*tail=pool,*g[MaxN];15 16 int n;17 LL m;18 LL h[MaxN][2];19 int fa[MaxN],f[MaxN][2];20 LL pre[MaxN],suf[MaxN];21 22 inline void make_edge(int u,int v){23     tail->v=v;tail->nxt=g[u];g[u]=tail++;24     tail->v=u;tail->nxt=g[v];g[v]=tail++;25 }26 27 inline int max(int a,int b){return a>b ? a : b;}28 void dp(){29     static int q[MaxN],l,r;30     memset(fa,0xff,sizeof(fa));31     for(fa[q[l=r=0]=1]=0;l<=r;l++)32         for(Node *p=g[q[l]];p;p=p->nxt) if(!~fa[p->v])33             fa[q[++r]=p->v]=q[l];34     for(int i=r;i>=0;i--){35         int u=q[i];36         int maxt=0xc0c0c0c0;37         int cnt=0,j;38         f[u][0]=0,f[u][1]=0;39         h[u][0]=1,h[u][1]=0;40         for(Node *p=g[u];p;p=p->nxt) if(p->v!=fa[u]){41             LL dt=0;42             f[u][0]+=max(f[p->v][0],f[p->v][1]);43             f[u][1]+=max(f[p->v][0],f[p->v][1]);44             maxt=max(maxt,f[p->v][0]+1-max(f[p->v][0],f[p->v][1]));45 46             if(f[p->v][0]>f[p->v][1]) dt=h[p->v][0];47             else if(f[p->v][0]<f[p->v][1]) dt=h[p->v][1];48             else dt=(h[p->v][0]+h[p->v][1])%m;49             pre[++cnt]=dt;suf[cnt]=dt;50             (h[u][0]*=dt)%=m;51         }52         pre[0]=suf[cnt+1]=1;53         for(int i=1;i<=cnt;i++) (pre[i]*=pre[i-1])%=m;54         for(int i=cnt;i;i--) (suf[i]*=suf[i+1])%=m;55         f[u][1]+=maxt;56         j=1;57         for(Node *p=g[u];p;p=p->nxt) if(p->v!=fa[u]){58             if(f[p->v][0]+1-max(f[p->v][0],f[p->v][1])==maxt)59                 (h[u][1]+=pre[j-1]*suf[j+1]%m*h[p->v][0]%m)%=m;60             j++;61         }62     }63     if(f[1][0]==f[1][1]) printf("%d\n%lld\n",f[1][0],(h[1][0]+h[1][1])%m);64     else if(f[1][0]>f[1][1]) printf("%d\n%lld\n",f[1][0],h[1][0]);65     else printf("%d\n%lld\n",f[1][1],h[1][1]);66 }67 int main()68 {69     scanf("%d",&n);70     for(int i=1;i<n;i++){71         int u,v;scanf("%d%d",&u,&v);72         make_edge(u,v);73     }74     scanf("%lld",&m);75     dp();76     return 0;77 }
View Code

细节反思:

1、求f和求g的过程可以一块写,思路比较清晰一点

2、求g[u][1]的时候的技巧:

  本渣只能想到先求所有的乘积,然后再枚举每一个位置的,除掉,因为取模只能求逆

  但此神犇的做法很厉害:

    先在求f的过程中把u的每个子节点的最优值记下来保存在数组中,并记下来u往叶子节点连边能得到的最大增值maxt

    然后把记最优值的数组从前往后累乘得到pre,从后往前乘得到suf

    然后对于每次枚举的连边的子节点i,首先判断连i所能得到的增值是否为maxt,如果是那么增加的方案数也就确定了:pre[i-1]*suf[i+1]*g[i][0]

细节方面真的很重要……

[vijos1892]树上的最大匹配(树形DP)