JDOJ2300 USACO2012 Feb Gold 3 Nearby Cows


题目大意:给你一棵树,树上每个点都有一群牛,这些牛会最多移动K距离,求每个点最多会出现多少牛。

这道题一看一棵树,还让你在树上求方案个数,很自然的就可以想到树形DP。

我们设f[i][j]表示在i的子树中距离小于等于j的牛的个数,g[i][j]表示在i的周围距离小于等于j的牛的个数。

之后我们先通过第一次DFS推出所有的f[i][j],之后g[1][k]=f[1][k],g[x][0]=v[x],剩下的就只能从上到下dp了。

我们已经知道子树中的答案,差的就是父树。

而如果父树中的点到to[i]的距离为k,那么这些点到x的距离必然为k-1.

于是我们就可以通过g[x][k-1]推出g[to[i]][k]。

然而这样当k≥2时会重复计算子树中的某些点,这些点到x的为k-1,那么到to[i]的距离必然为k-2。

这样就再减去f[to[i]][k-2]即可。

最终状态转移方程就为g[to[i]][k]=f[to[i]][k]+g[x][k-1]-f[to[i]][k-2]。

最后答案就是∑g[i][j] (0≤j≤k)

#include <bits/stdc++.h>
using namespace std;
int n,k,ans,top,inx,iny,to[200100],nex[200100],head[100100],c[100100],f[100100][50],g[100100][50];
void addedge(int tx,int ty)
{
    to[++top]=ty,nex[top]=head[tx],head[tx]=top;return;
}
void dfsa(int pos,int from)
{
    f[pos][0]=c[pos];
    for(int i=head[pos];i;i=nex[i])
    {
        if(to[i]==from) continue;
        dfsa(to[i],pos);
        for(int j=1;j<=k;++j) f[pos][j]+=f[to[i]][j-1];
    }
    return;
}
void dfsb(int pos,int from)
{
    for(int i=head[pos];i;i=nex[i])
    {
        if(to[i]==from) continue;
        for(int j=1;j<=k;++j)
        {
            g[to[i]][j]=f[to[i]][j]+g[pos][j-1];
            if(j>=2) g[to[i]][j]-=f[to[i]][j-2];
        }
        dfsb(to[i],pos);
    }
    return;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;++i) scanf("%d%d",&inx,&iny),addedge(inx,iny),addedge(iny,inx);
    for(int i=1;i<=n;++i) scanf("%d",c+i);
    dfsa(1,0);
    for(int i=1;i<=k;++i) g[1][i]=f[1][i];
    for(int i=1;i<=n;++i) g[i][0]=c[i];
    dfsb(1,0);
    for(int i = 1 ; i <= n ; i ++ )
    {
        ans = 0;
        for(int j = 0 ; j <= k ; j ++ )
            ans += g[i][j];
        printf("%d\n" , ans);
    }
    return 0;
}

 

声明:TonyZhao's Home|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - JDOJ2300 USACO2012 Feb Gold 3 Nearby Cows


不骗了,不骗了。
A Simple OIer fighting tooth and nail.