[NOI2008 day1 设计路线]树形动态规划

【算法分析】

算是NOI里比较简单的DP

首先应当注意到，只有个3叉以上了分裂点，才会出现不舒适值。所以可以推测不舒适值<=lgN。

于是我们可以枚举不舒适值，进行dp

定义：

f[p][0][ans]为在p点，和儿子没有接轨，最大不舒适度为ans的方案数。

f[p][1][ans]为在p点，和1个儿子有接轨，最大不舒适度为ans的方案数。

f[p][2][ans]为在p点，和2个儿子有接轨，最大不舒适度为ans的方案数。

然后进行树形dp

令T1=f[j][0][ans]+f[j][1][ans]

T2=f[j][0][ans-1]+f[j][1][ans-1]+f[j][2][ans-1]

然后转移：

f[i][2][ans]=f[i][1][ans]*T1+f[i][2][ans]*T2;

f[i][1][ans]=f[i][0][ans]*T1+f[i][1][ans]*T2;

f[i][0][ans]=f[i][0][ans]*T2;

枚举ans，然后判断方案数是否>0，是的输出。

【其它】表示WA了一遍，那个mod=0的bug实在太猥琐了，于是我搞到如果是mod回来=0的话，就=Mod

【CODE】

#include const __int64 N=101111;
struct gtp{__int64 y,next;}g[N*2];
__int64 n,m,Mod,e,ans;
__int64 ls[N],f[N][3][11];

inline void mod(__int64 &x){
    if (x%Mod==0 && x>0) x=Mod;
                    else x=x%Mod;
}   

void dp(__int64 p,__int64 fa){
    f[p][0][ans]=1;
    for (__int64 t=ls[p];t;t=g[t].next)
      if (g[t].y!=fa){
        dp(g[t].y,p);
        __int64 T1,T2;
        T1=(f[g[t].y][0][ans]+f[g[t].y][1][ans]); mod(T1);
        T2=(f[g[t].y][0][ans-1]+f[g[t].y][1][ans-1]+f[g[t].y][2][ans-1]); mod(T2);
        f[p][2][ans]=(f[p][2][ans]*T2+f[p][1][ans]*T1); mod(f[p][2][ans]);
        f[p][1][ans]=(f[p][1][ans]*T2+f[p][0][ans]*T1); mod(f[p][1][ans]);
        f[p][0][ans]=f[p][0][ans]*T2; mod(f[p][0][ans]);
    }   
}   

void work(){
    for (ans=1;;ans++){
        dp(1,0);
        if (f[1][0][ans]+f[1][1][ans]+f[1][2][ans]){
            printf("%dn",ans-1);
            printf("%dn",(f[1][0][ans]+f[1][1][ans]+f[1][2][ans])%Mod);
            return;
        }   
    }   
}   

void add(__int64 x,__int64 y){
    e++;
    g[e].y=y; g[e].next=ls[x]; ls[x]=e;
}   

int main(){
    freopen("design.in","r",stdin);
    freopen("design.out","w",stdout);
    scanf("%I64d%I64d%I64d",&n,&m,&Mod);
    if (m!=n-1){
        printf("-1n");
        printf("-1n");
        return 0;
    }   
    for (__int64 i=1;i<=m;i++){
        __int64 x,y;
        scanf("%I64d%I64d",&x,&y);
        add(x,y);
        add(y,x);
    }   
    work();
}