二分答案，问题就转化为了一个可行性问题，因为我们不知道国王会往哪里走，所以我们要在所有他可能走到的点建造，考虑用树形DP解决(这个DP还是比较好写的，你看我这个不会DP的人都能写出来=。=)
定义$dp[x]$表示以$x$这个点为根的子树中(不包含x)需要修建的次数(因为1号点已经修好了，最后回来不用管)，那么对于每个二分出的$mid$有$dp[x]=max((sum dp[son[i]])+sons[x]-mid)$，其中$sons[i]$表示它(直接的)儿子的个数，显然对于每个点是必须先把所有儿子建好的。最后如果$dp[1]=0$说明可行
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=300005; 6 int n,t1,t2,cnt,l,r,mid,ans; 7 int p[N],noww[2*N],goal[2*N]; 8 int son[N],dp[N]; 9 void link(int f,int t) 10 { 11 noww[++cnt]=p[f]; 12 goal[cnt]=t,p[f]=cnt; 13 } 14 void MARK(int nde,int fth) 15 { 16 for(int i=p[nde];i;i=noww[i]) 17 if(goal[i]!=fth) MARK(goal[i],nde),son[nde]++; 18 } 19 void DFS(int nde,int fth) 20 { 21 int tmp=0; 22 for(int i=p[nde];i;i=noww[i]) 23 if(goal[i]!=fth) DFS(goal[i],nde),tmp+=dp[goal[i]]; 24 dp[nde]=max(tmp+son[nde]-mid,0); 25 } 26 bool check(int x) 27 { 28 memset(dp,0xcf,sizeof dp); 29 DFS(1,0); return !dp[1]; 30 } 31 int main () 32 { 33 scanf("%d",&n),r=n; 34 for(int i=1;i<n;i++) 35 { 36 scanf("%d%d",&t1,&t2); 37 link(t1,t2),link(t2,t1); 38 } 39 MARK(1,0); 40 while(l<=r) 41 { 42 mid=(l+r)/2; 43 if(check(mid)) r=mid-1,ans=mid; 44 else l=mid+1; 45 } 46 printf("%d",ans); 47 return 0; 48 }