题解 P3047 【[USACO12FEB]附近的牛Nearby Cows】

· · 题解

这道题我花了很久才做出来，自己一开始也没想清楚，求助了大佬们

这道题有两种思路

一种在大佬的博客上，我算是明白了，干脆贴上博客吧，我将也讲不清笑哭

http://blog.csdn.net/oi\_konnyaku/article/details/75449966

另一种呢，是比较容易想到的，但也很容易出错的

用到了链式前向星和容斥原理

首先链式前向星呢，是个高级的东西，百度上第一个候选的博客挺好的

实际上也就是记录边的信息，记录该边同起点异终点的边的存储位置和该边的权值以及指向的终点

这个不太好理解，模拟也需要一定的耐心，但是搞懂了真的很好用

这是我第一道用链式前向星做的题，比较简单的例题大家可以去做一下##二叉苹果数

容斥原理呢，我也不太清楚，百度上是这么说的

然后来了一大堆看不懂的sigma等等，看得懂的只有这个

所以大概明白了

递推（DP）公式就能够理解了

具体的吧，建议首次用链式前向星可以照着代码敲

我的注释也是比较详尽的啦~(≧▽≦)/~（因为第一遍自己也没搞清楚）

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int read()//读入优化
{
    char ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    int h=0;
    while(ch>='0'&&ch<='9')
    {
        h=h*10+ch-'0';
        ch=getchar();
    }
    return h;
}
int f[100001][21];//f[i][j]表示距离第i块地(正好)j步的牛的头数 
int w[100001];//存储结点的牛的头数 
struct qxx{
    int to;
    int next;//链式前向星 
}a[200002];
int head[100001];
int cnt=0;//计数 
int fa[100001]; 
int n,k; 
void add(int x,int y)
{
    a[++cnt].to=y;
    a[cnt].next=head[x];
    head[x]=cnt;
}
void dfs(int x,int y)//实际上这个函数默认1为根，进行树形深搜 
{
    fa[x]=y;
    f[x][0]=w[x];//当前结点走0步
    for(int i=head[x];i!=-1;i=a[i].next)//枚举同起点异终点的边

{//申明此时变量：x表示当前结点，fa表示x的父结点 //i表示枚举以x为起点的边的编号，a[i].to表示第i条边的终点(x的子结点)

     //a[i].next前向星指向下一条以x为起点的边 
        if(a[i].to!=y)
        {
            dfs(a[i].to,x);//深搜子结点 
            for(int j=1;j<=k;j++)
            {
                f[x][j]+=f[a[i].to][j-1];//先加上子树上的牛 
            }
        }
    } 
}
int main()
{
//    freopen("a.in","r",stdin);
//    freopen("a.out","w",stdout);
    n=read();k=read();
    for(int i=0;i<=100000;i++) head[i]=-1; 
    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        x=read();
        y=read();
        add(x,y);
        add(y,x);//双向存储链式前向星 
    }
    for(int i=1;i<=n;i++) w[i]=read();//读取每个结点的牛的数量
    dfs(1,0); 
//    for(int i=1;i<=n;i++) for(int w=0;w<=k;w++) cout<<"f["<<i<<"]["<<w<<"]="<<f[i][w]<<endl; 
    for(int i=1;i<=n;i++)
        for(int w=1;w<=k;w++)
            f[i][w]+=f[i][w-1];//计算前缀和，改变f的意义
//    for(int i=1;i<=n;i++) for(int w=0;w<=k;w++) cout<<"f["<<i<<"]["<<w<<"]="<<f[i][w]<<endl;//这两句用来调试的
    //现在f[i][j]表示在i结点的子树上距离为j的牛数
    for(int i=1;i<=n;i++)//顺序枚举田地 
    {
        int ans=f[i][k];//初值赋为从1开始，子树上距离为k以内的牛数 
        int j=k;//
        int x=i;//
        //实际上一整句话的意思是
        //运用容斥原理，从x结点开始，ans为向父结点走0~k步再加上父结点向下走k~0步的和，再减去重复算的(重复算的是子树上走j-2步的地方)
        //比如说按样例，当i为2时，x=2，ans首先为3+4+6+2=15，keep on，ans+=f[fa[2](1)][j-1(1)],ans+=1+2+5=8,ans-=f[2][0](2),算得ans=21
        //实际上就是通过找父结点拓展出兄弟结点的情况，由于父结点的状态包括了该子树的状态，故要减 
        while(x!=1&&j!=0)
        {
            ans+=f[fa[x]][j-1];
            if(j>=2) ans-=f[x][j-2];
            x=fa[x];
            j--;
        }
        printf("%d\n",ans); 
    } 
    return 0;
}