题目链接：Kingdom’s Power
题目大意：n个点构成一颗树，1号点是大本营可以无限派兵，每次可以移动一个军队走1步，问走遍n个点最少需要几步。
思路： 很容易想到这是一道树上DP的题，问题是我们每个结点应该维护什么值，以及结点间状态的转移。我们可以知道，如果我们要到达某个点，有两种方案，一种是调用已经派遣出去的军队，折返到达，一种是重新从起始点派兵，所以很容易想到要维护已经出去的军队和当前点的距离。那么我们对于每一颗节点维护2个值，一个是走完子树所有点用的最少总步数（默认此处初始时有一只军队），一个是当前子树中距离它最近的军队与它的距离，至于为什么维护最近的一个就可以，会在后文解释。
那么，我们使用dfs进行搜索，在最底层，节点的值会是（0，0），再不断回溯，更新父节点的值。对于当前节点，遇到第一个子节点时，值直接变成（vx+1,vy+1）,也就是直接走下去，然后标记一下flag=true，遇到后面的子结点的时候，相当于（ux,uy）和（vx+1,vy+1）两个状态的合并过程。
这里我们就要进行分类讨论了，一共有三种情况。
第一种是从u最近子节点中的已经派出的军队折返到达，那么ux = ux+uy+vx+1，uy=vy+1，也就是折返走掉v，更新最近的位置为vy+1；第二种是从起点重新发兵，那么ux = ux+dis[u]+vx+1，uy = min(uy,vy+1)，这里对于uy只用维护一个最小值即可，因为被筛掉的那个值一定比dis[u]大，所以下次更新的时候也一定不会被选择，可以直接舍弃那只军队；第三种情况则是改变初始行走策略，先走v，原因是从v走完后离u最近的点折返更划算，也就是vy+1<=uy，那么我们更新ux = ux+vx+1+vy+1，uy = uy。很容易可以推出：当uy<=dis[u]&&uy<=vy+1的时候采取第一种情况，当dis[u]<=uy&&dis[u]<=vy+1的时候采取第二种情况，当vy+1<=uy&&vy+1<=dis[u]的时候采取第三种情况。最后的答案就是1号节点的状态值。
提醒： 本题多组数据，且数据量较大，记得清空数组，且不要用memset清空！！！
下面是我的AC代码：
#include<iostream> #include<stdio.h> using namespace std; int T; struct node{ int v,next; }a[4000005]; int head[1000005]; int e = -1; int dis[1000005]; int ans1[1000005]; int ans2[1000005]; void addnode(int u,int v){ a[++e].v = v; a[e].next = head[u]; head[u] = e; } bool vis[1000005]; void dfs(int x){//预处理距离 vis[x] = true; for(int i=head[x];i!=-1;i=a[i].next){ int v=a[i].v ; if(vis[v])continue; dis[v]=dis[x]+1; dfs(v); } } long long ans = 0; void work(int x){ ans1[x]=ans2[x]=0; vis[x]=true; bool flag = false; for(int i=head[x];i!=-1;i=a[i].next){ int v = a[i].v; if(vis[v])continue; work(v); int tmpx=ans1[v]+1; int tmpy=ans2[v]+1; if(!flag){ ans1[x]=tmpx; ans2[x]=tmpy; flag = true; } else if(ans2[x]<=tmpy&&ans2[x]<=dis[x]){//最近军队折返 ans1[x]=ans1[x]+tmpx+ans2[x]; ans2[x]=tmpy; } else if(dis[x]<=ans2[x]&&dis[x]<=tmpy){//从起点发兵 ans1[x]=ans1[x]+dis[x]+tmpx; ans2[x]=min(ans2[x],tmpy); } else if(tmpy<=ans2[x]&&tmpy<=dis[x]){//先走当前点 ans1[x]=ans1[x]+tmpx+tmpy; } } // cout<<x<<" "<<ans1[x]<<" "<<ans2[x]<<" "<<dis[x]<<endl; } int main(){ scanf("%d",&T); for(int Case = 1;Case<=T;Case++){ int n; scanf("%d",&n); for(int i=1;i<=n;i++){ head[i]=-1; vis[i]=false; } e = -1; for(int i=2;i<=n;i++){ int v; scanf("%d",&v); addnode(i,v); addnode(v,i); } dis[1]=0; dfs(1); for(int i=1;i<=n;i++) vis[i]=false; work(1); printf("Case #%d: %d\n",Case,ans1[1]); } }