[APIO2010 patrol]树形动态规划

【题目地址】http://www.apio.olympiad.org/
【算法分析】
就是求两（一）条不相交的最长链。
F[i][j][k]表示i这个结点，已完成的链有j条，k表示有无一条只有一边的可延伸链，所得到的最大长度。
然后就像背包一样转移。
【CODE】
#include #include #include const int N=100005;
struct edge{int x,y;edge *next;}sp[N*2],*ls[N];
int n,L,e,tot;
int F[N][3][2],pF[3][2];

inline void addedge(int x,int y){
sp[++e].x=x; sp[e].y=y; sp[e].next=ls[x]; ls[x]=&sp[e];
}

void init(){
e=0;
memset(ls,0,sizeof(ls));
int i,x,y;
scanf("%d%d",&n,&L);
for (i=1;i scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
}

inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa) dp(t->y,t->x);
F[p][0][0]=0;
F[p][0][1]=0;
int j,k,pj,pk;
tot=0;
for (edge *t=ls[p];t;t=t->next) if (t->y!=fa){
memcpy(pF,F[p],sizeof(pF));
for (j=0;j<=L;j++)
for (pj=0;pj+j<=L;pj++){
F[p][pj+j][0]=max(F[p][pj+j][0],pF[pj][0]+F[t->y][j][0]);
F[p][pj+j][1]=max(F[p][pj+j][1],pF[pj][0]+F[t->y][j][1]+1);
F[p][pj+j][1]=max(F[p][pj+j][1],pF[pj][1]+F[t->y][j][0]);
if (pj+j+1<=L)
F[p][pj+j+1][0]=max(F[p][pj+j+1][0],pF[pj][1]+F[t->y][j][1]+1);
}
}
}

void solve(){
int ans=0;
memset(F,200,sizeof(F));
dp(1,0);
ans=max(ans,F[1][1][0]);
ans=max(ans,F[1][0][1]);
if (L==2){
ans=max(ans,F[1][1][1]);
ans=max(ans,F[1][2][0]);
}
printf("%dn",2*n-2-ans+L);
}

int main(){
freopen("patrol.in","r",stdin);
freopen("patrol.out","w",stdout);
init();
solve();
return 0;
}