题目链接：点击打开链接
题目中给出了一个关键的提示：设这棵树的最长链的点个数为K的时候，答案为K或者K+1
那么可以这么考虑·；验证答案能否为K，能的话答案就是K，否则答案就为K+1。
那么问题便转换为，给那些无向边以方向，问能否使最长链的点的个数为K。
首先先预处理出最长链的点的个数K以及其中一条最长链的第一个点D。
在这里为了方便起见，人为地定义了每个点的深度d，并规定点D的深度为1，所有有向边中被指向的点的深度必定大于指向它的点的深度。
那么问题便进一步转换为，能否给树中的无向边方向使得所有的点的深度均在区间[1,K]内。
将树拉为以D为根的树，便可以进行dp了。
设dp[pos][c]为，当点pos的深度为K的时候，以点pos为根的子树能否满足条件。
状态转移也能够很容易的得到：
设pos的一个儿子为son，
如果pos指向son的话，其儿子可能的状态只有dp[son][c+j]（j.>0，下同）；
如果son指向pos的话，其儿子可能的状态只有dp[son][c-j]；
如果pos跟son之间的连边是无向边的话，其儿子可能的状态就有dp[son][c+j]和dp[son][c-j]；
当pos的儿子中有一个dp值为真的时候其dp值便为真，否则便为假。
记忆化搜索一波就可以了。
代码如下：
#include<bits/stdc++.h> using namespace std; struct edge { int u,v; int w;//0:u->v 1:u--v 2:u<-v edge(int uu=0,int vv=0,int ww=0):u(uu),v(vv),w(ww){} }; vector<edge> e[2005]; int MaxD[2005]; bool vis[2005][2005]; bool dp[2005][2005]; int n,K; void input(int p) { n=p; char s[10]; do { n=max(n,p); while(scanf("%s",s)==1) { if(s[0]=='0')break; int pp=0; char c='k'; int len=strlen(s); for(int i=0;i<len;i++) { if(s[i]>='0'&&s[i]<='9') { pp*=10; pp+=(s[i]-'0'); } else c=s[i]; } n=max(n,pp); if(c=='k') { e[p].push_back(edge(p,pp,1)); e[pp].push_back(edge(pp,p,1)); } else if(c=='d') { e[p].push_back(edge(p,pp,0)); e[pp].push_back(edge(pp,p,2)); } else { e[p].push_back(edge(p,pp,2)); e[pp].push_back(edge(pp,p,0)); } } scanf("%d",&p); }while(p!=0); } void Pre_dfs(int pos) { if(MaxD[pos]!=-1)return; MaxD[pos]=1; for(int i=0;i<e[pos].size();i++) { edge &p=e[pos][i]; if(p.w!=0)continue; Pre_dfs(p.v); MaxD[pos]=max(MaxD[pos],MaxD[p.v]+1); } } bool dfs(int prt,int pos,int c) { if(c<1||c>K)return false; if(vis[pos][c])return dp[pos][c]; vis[pos][c]=true; dp[pos][c]=true; for(int i=0;i<e[pos].size();i++) { edge &p=e[pos][i]; if(p.v==prt)continue; if(p.w==0) { bool pans=false; for(int j=1;(!pans)&&c+j<=K;j++) pans=pans||dfs(pos,p.v,c+j); dp[pos][c]=dp[pos][c]&&pans; } else if(p.w==2) { bool pans=false; for(int j=1;(!pans)&&c-j>=1;j++) pans=pans||dfs(pos,p.v,c-j); dp[pos][c]=dp[pos][c]&&pans; } else { bool pans=false; for(int j=1;(!pans)&&c+j<=K;j++) pans=pans||dfs(pos,p.v,c+j); for(int j=1;(!pans)&&c-j>=1;j++) pans=pans||dfs(pos,p.v,c-j); dp[pos][c]=dp[pos][c]&&pans; } } return dp[pos][c]; } int main() { int p; while(scanf("%d",&p)==1&&p) { for(int i=1;i<=2000;i++) e[i].clear(); input(p); memset(MaxD,-1,sizeof(MaxD)); for(int i=1;i<=n;i++) Pre_dfs(i); int mx=1; for(int i=2;i<=n;i++) if(MaxD[i]>MaxD[mx]) mx=i; K=MaxD[mx]; memset(vis,0,sizeof(vis)); if(dfs(-1,mx,1))printf("%d\n",K); else printf("%d\n",K+1); } }