poj 2057 樹形dp

這個題目需要先推出已知順序下的遞推計算公式，然後再通過計算交換相鄰兩項的內插補點來找出貪心的政策。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=1e3+9;
int fa[maxn],fb[maxn],leaves[maxn];
bool is[maxn];
int head[maxn],lon;
struct N
{
    int id;
    int fb,leaves;
    bool operator <(const struct N & xx) const
    {
        return fb*xx.leaves<xx.fb*leaves;
    }
};
struct
{
    int next,to;
}e[maxn<<1];
void edgeini()
{
    memset(head,-1,sizeof(head));
    lon=-1;
}
void edgemake(int from,int to)
{
    e[++lon].to=to;
    e[lon].next=head[from];
    head[from]=lon;
}

void dfs(int t)
{
    fa[t]=0;
    fb[t]=0;
    leaves[t]=0;
    if(head[t]==-1)
    {
        leaves[t]=1;
        return ;
    }
    for(int k=head[t];k!=-1;k=e[k].next)
    dfs(e[k].to);

    for(int k=head[t];k!=-1;k=e[k].next)
    {
        int u=e[k].to;
        fa[t]+=fa[u]+leaves[u];
        fb[t]+=fb[u]+2;
        leaves[t]+=leaves[u];
    }

    N xx;
    priority_queue <N> q;
    while(!q.empty()) q.pop();
    for(int k=head[t];k!=-1;k=e[k].next)
    {
        xx.id=e[k].to;
        xx.fb=fb[e[k].to]+2;
        xx.leaves=leaves[e[k].to];
        q.push(xx);
    }

    int k=0;
    while(!q.empty())
    {
        int u=q.top().id;
        q.pop();
        fa[t]+=(fb[u]+2)*k;
        k+=leaves[u];
    }
    if(is[t]) fb[t]=0;
}

int main()
{
    int n;
    while(scanf("%d",&n),n)
    {
        edgeini();
        char s[10];
        for(int i=1,from;i<=n;i++)
        {
            scanf("%d %s",&from,s);
            if(from!=-1)
            edgemake(from,i);
            if(s[0]=='N') is[i]=0;
            else is[i]=1;
        }
        dfs(1);
        double ans=fa[1];
        ans/=leaves[1];
        printf("%.4f\n",ans);
    }
    return 0;
}