【UVALive4685-Succession】树形DP

http://acm.hust.edu.cn/vjudge/problem/14338

题意：给定一棵树，每个点有一个值，让你选择k个点，并且这k个点是连在一起的（从任意一个点出发，可以遍历完所有选择的点并且不经过没有被选择的点），让这k个点的价值总和最大，纹方案数（Mod1000000007）。

题解：设d[x][k]为必须选择x，以x为根的子树中共选择了k个节点，价值总和最大是多少。

f[x][k]为d[x][k]对应的方案数是多少。

对于x，我们把x的孩子son不断地并到f[x]中。

对于每一个son：d[x][j]=maxx(d[x][j-k],d[son][k]);

需要注意的就是上式中d[x][j]不断地变化，对于当前的son，j变大的时候可能用到的d[x][j-k]是用当前的son更新的。所以要开一个p[x][j]等于当前的son没更新x的时候d[x][j]的值，同理q[x][j]=f[x][j]。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 const int N=;

 const LL Inf=(LL)1e9,Mod=;

 struct node{

     int x,y,next;

 }a[*N];

 int len,n,m,r;

 int first[N],son[N],w[N];

 LL a1,a2,d[N][N],f[N][N],p[N][N],q[N][N];

 void ins(int x,int y)

 {

     len++;

     a[len].x=x;a[len].y=y;

     a[len].next=first[x];first[x]=len;

 }

 void dfs(int x,int fa)

 {

     son[x]=;

     for(int i=first[x];i;i=a[i].next)

     {

         int y=a[i].y;

         if(y==fa) continue;

         dfs(y,x);

         son[x]+=son[y];

     }

 }

 void copy(int x)

 {

     for(int i=;i<=n;i++) p[x][i]=d[x][i],q[x][i]=f[x][i];

 }

 void dp(int x,int fa)

 {

     for(int i=;i<=n;i++) d[x][i]=-Inf;

     memset(f[x],,sizeof(f[x]));

     d[x][]=;f[x][]=;d[x][]=w[x];f[x][]=;

     copy(x);

     for(int i=first[x];i;i=a[i].next)

     {

         int y=a[i].y;

         if(y==fa) continue;

         dp(y,x);

         for(int j=;j<=son[x];j++)

         {

             for(int k=;k<=son[y] && (j-k)>=;k++)

             {

                 LL dd=p[x][j-k]+d[y][k];

                 LL ff=(q[x][j-k]*f[y][k])%Mod;

                 if(dd > p[x][j])

                 {

                     if(dd>d[x][j]) d[x][j]=dd,f[x][j]=ff;

                     else if(dd==d[x][j]) f[x][j]=(f[x][j]+ff)%Mod;

                 }

                 else if(dd == p[x][j])

                 {

                     if(dd==d[x][j]) f[x][j]=(f[x][j]+ff)%Mod;

                 }

             }

         }

         copy(x);

     }

     if(d[x][m]>a1) a1=d[x][m],a2=f[x][m];

     else if(d[x][m]==a1) a2=(a2+f[x][m])%Mod;

 }

 int main()

 {

     freopen("a.in","r",stdin);

     // freopen("a.out","w",stdout);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         len=;

         memset(first,,sizeof(first));

         scanf("%d%d%d",&n,&m,&r);

         for(int i=;i<=n;i++) scanf("%d",&w[i]);

         for(int i=;i<=r;i++)

         {

             int x,y;

             scanf("%d%d",&x,&y);

             x++;y++;

             ins(x,y);ins(y,x);

         }

         dfs(,);

         a1=-Inf;

         dp(,);

         printf("%I64d %I64d\n",a1,a2);

     }

     return ;

 }

巴特西

【UVALive4685-Succession】树形DP

最新文章

热门文章