hdu 4582ツリーDP

構想:まず声明します.私は参考にします.http://blog.csdn.net/frog1902/article/details/9921845この大牛のブログです.
彼の話はもう詳しくなりましたが、やはりいくつか補足したいです.
彼の解題報告を見てから私のほうがいいです.
私のこのback[i]は彼のlim[i]に対してです.
私が追加したいのは、バック[i]は本当のバック[i]ではなく、この行のコードを見ることができます.バック[u]=max(back[u],dep[v]+1);つまり、それは祖ノードに戻り、さらに下のノードに戻るということです.
リターン・サイドがない点については、バックノードがルートノードにあることに相当し、ノードからルートノードのいずれかのエッジが選択されても良い.
dpの場合は、まずdp[u][i](=i<=dep[u])を0にし、uからback[u]までの間にもう一方のノードが選択されているという意味で、サブノードがあることを考慮しないと、必要な辺数は0となる.dp[u][dep[u]++の意味は、dep[u]を親ノードの端に選択する点がu自身であるということです.
私が一番理解しにくいのはdp[u][j]に対して、dp[v]と0<=k==jの深さの中から一番小さいdp[v][k]を選んで、dp[u][j]の値を求めることです.
dp[u][j]の意味は、親ノードの側に深さjのノードが選択された後、uを根とする子樹はどれぐらいの辺が必要かということであるので、この値、つまり、深さjのノードを親ノードの側に選択した後、そのサブノードを根とするdp[v][j]がすでに確定している必要がある.(前提はすべての選択は合法的でなければなりません.合法的なのはこの辺がback[u]からuの道にあるということです.)

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<vector>

#define Maxn 2010

using namespace std;

int dp[Maxn][Maxn],dep[Maxn],back[Maxn],n,m,vi[Maxn];

vector<int> head[Maxn];

void init()

{

    memset(dp,-1,sizeof(dp));

    memset(dep,0,sizeof(dep));

    memset(vi,0,sizeof(vi));

    memset(back,0,sizeof(back));

    for(int i=0;i<=n;i++)

        head[i].clear();

}

void add(int u,int v)

{

    head[u].push_back(v);

    head[v].push_back(u);

}

void dfs(int u)

{

    int i,v,sz;

    vi[u]=1;

    sz=head[u].size();

    for(i=0;i<sz;i++)

    {

        v=head[u][i];

        if(vi[v]) continue;

        dep[v]=dep[u]+1;

        dfs(v);

    }

}

void Treedp(int u)

{

    int i,v,sz,j;

    vi[u]=1;

    sz=head[u].size();

    for(i=back[u];i<=dep[u];i++)

        dp[u][i]=0;

    for(i=0;i<sz;i++)

    {

        v=head[u][i];

        if(vi[v]) continue;

        Treedp(v);

        int temp=dp[v][dep[v]];

        for(j=0;j<=dep[u];j++)

        {

            if(dp[v][j]!=-1)

            {

                if(temp!=-1)

                    temp=min(temp,dp[v][j]);

                else

                    temp=dp[v][j];

            }

            if(j>=back[u])

            {

                if(temp!=-1)

                    dp[u][j]+=temp;

            }

        }

    }

    if(u!=1)

    dp[u][dep[u]]++;

}

int main()

{

    int i,j,u,v;

    while(scanf("%d%d",&n,&m)!=EOF,n||m)

    {

        init();

        for(i=1;i<n;i++)

        {

            scanf("%d%d",&u,&v);

            add(u,v);

        }

        dfs(1);

        for(i=n;i<=m;i++)

        {

            scanf("%d%d",&u,&v);

            if(dep[u]<dep[v])

                swap(u,v);

            back[u]=max(back[u],dep[v]+1);

        }

        memset(vi,0,sizeof(vi));

        Treedp(1);

        printf("%d
",dp[1][0]);

    }

    return 0;

}