当然如果你想像考场上傻掉的我一样打树上dp，那祝你码得愉快了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define set(p) memset(dp[p],0x3f,sizeof(dp[p]))
 4 int dp[100005][5][5],n,fir[100005],l[200005],to[200005],cnt,k,p;
 5 void connect(int a,int b){
 6     l[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;
 7     l[++cnt]=fir[b];fir[b]=cnt;to[cnt]=a;
 8 }
 9 void dfs(int p,int f){
10     for(int ii=fir[p];ii;ii=l[ii])if(to[ii]!=f)dfs(to[ii],p);
11     int t=100002,tt=100003;set(t);memset(dp[t],0,sizeof(dp[t]));dp[t][0][0]=1;
12     for(int ii=fir[p];ii;ii=l[ii])if(to[ii]!=f){
13         t^=1;tt^=1;set(t);
14         for(int i=0;i<=k+1;++i)for(int j=0;j<=k;++j)
15             dp[t][0][0]=min(dp[t][0][0],dp[tt][0][0]+dp[to[ii]][i][j]);
16         for(int i=0;i<=k+1;++i)for(int j=0;j<=k;++j)
17             for(int x=0;x<=k+1;++x)for(int y=0;y<=k;++y) if(x+j<=k&&i+y<=k)
18                 dp[t][min(i,x+1)][max(j,y+1)]=min(dp[t][min(i,x+1)][max(j,y+1)],dp[tt][i][j]+dp[to[ii]][x][y]);
19         for(int i=0;i<=k+1;++i)for(int j=0;j<k;++j)dp[t][i][j+1]=min(dp[t][i][j+1],dp[t][i][j]);
20         for(int i=0;i<=k;++i)for(int j=0;j<=k;++j)dp[t][i+1][j]=min(dp[t][i+1][j],dp[t][i][j]);
21     }
22     for(int i=0;i<=k+1;++i)for(int j=0;j<=k;++j)dp[p][i][j]=dp[t][i][j];
23     for(int i=0;i<=k+1;++i)for(int j=0;j<k;++j)dp[p][i][j+1]=min(dp[p][i][j+1],dp[p][i][j]);
24     for(int i=0;i<=k;++i)for(int j=0;j<=k;++j)dp[p][i+1][j]=min(dp[p][i+1][j],dp[p][i][j]);
25 }
26 int main(){
27     scanf("%d%d%d",&n,&k,&p);
28     for(int i=1,a,b;i<n;++i)scanf("%d%d",&a,&b),connect(a,b);
29     dfs(1,0);int ans=0x3f3f3f3f;
30     for(int i=0;i<=k+1;++i)for(int j=0;j<=k;++j)ans=min(ans,dp[1][i][j]);
31     printf("%d\n",ans);
32 }

先交的40分。只能处理k=1的树上dp

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define set(p) memset(dp[p],0x3f,sizeof(dp[p]))
 4 int dp[100005][11][11],n,fir[100005],l[200005],to[200005],cnt,k,p;
 5 void connect(int a,int b){
 6     l[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;
 7     l[++cnt]=fir[b];fir[b]=cnt;to[cnt]=a;
 8 }
 9 void dfs(int p,int f){
10     for(int ii=fir[p];ii;ii=l[ii])if(to[ii]!=f)dfs(to[ii],p);
11     int t=100002,tt=100003;set(t);dp[t][k][0]=0;dp[t][0][0]=1;
12     for(int ii=fir[p];ii;ii=l[ii])if(to[ii]!=f){
13         t^=1;tt^=1;set(t);
14         for(int i=0;i<=k+1;++i)for(int j=0;j<=k;++j)
15             dp[t][0][0]=min(dp[t][0][0],dp[tt][0][0]+dp[to[ii]][i][j]);
16         for(int i=0;i<=k+1;++i)for(int j=0;j<=k;++j)
17             for(int x=0;x<=k+1;++x)for(int y=0;y<=k;++y) if(x+j<=k&&i+y<=k)
18                 dp[t][min(i,x+1)][max(j,y+1)]=min(dp[t][min(i,x+1)][max(j,y+1)],dp[tt][i][j]+dp[to[ii]][x][y]);
19         for(int i=0;i<=k+1;++i)for(int j=0;j<k;++j)dp[t][i][j+1]=min(dp[t][i][j+1],dp[t][i][j]);
20         for(int i=0;i<=k;++i)for(int j=0;j<=k;++j)dp[t][i+1][j]=min(dp[t][i+1][j],dp[t][i][j]);
21     }
22     for(int i=0;i<=k+1;++i)for(int j=0;j<=k;++j)dp[p][i][j]=dp[t][i][j];
23     for(int i=0;i<=k+1;++i)for(int j=0;j<k;++j)dp[p][i][j+1]=min(dp[p][i][j+1],dp[p][i][j]);
24     for(int i=0;i<=k;++i)for(int j=0;j<=k;++j)dp[p][i+1][j]=min(dp[p][i+1][j],dp[p][i][j]);
25 }
26 int main(){
27     scanf("%d%d%d",&n,&k,&p);
28     for(int i=1,a,b;i<n;++i)scanf("%d%d",&a,&b),connect(a,b);
29     dfs(1,0);int ans=0x3f3f3f3f;
30     for(int i=0;i<=k+1;++i)for(int j=0;j<=k;++j)ans=min(ans,dp[1][i][j]);
31     printf("%d\n",ans);
32     for(int i=1;i<=n;++i){printf("%d:\n",i);
33         for(int j=0;j<=k+1;++j){for(int x=0;x<=k;++x)printf("%d ",dp[i][j][x]==0x3f3f3f3f?-8:dp[i][j][x]);puts("");}
34         puts("");
35     }
36 }

盖掉它的0分代码（没删调试语句）实际上是20分）

当然贪心这种东西除非会证明不然是真的不敢打。上次的T1就没发现那是一个贪心然而证明了正确性。。。

当然这次根本没有往那个方向上去想。

这个写的太好了。我无法反驳（因为它就是对的）

所以，就没了！

我们只需要维护一个数组f，表示从这个点开始多大的范围内能都被控制。

那么我们在一个新的位置上设置守卫时这个位置的f就是k

尝试更新与它相邻的点，它们的f在已有的f和k-1中取max就好。

然后同理继续向外扩散就好了。初值要赋成-1，那么f！=-1就表示这个点已经被看守了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 priority_queue<pair<int,int> >q;
 4 int res[100005],cnt,n,k,t,fir[100005],l[200005],to[200005],f[100005],ans;
 5 void link(int a,int b){l[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;}
 6 void pre_dfs(int p,int fa,int dep){
 7     q.push(make_pair(dep,p));res[p]=-1;f[p]=fa;
 8     for(int i=fir[p];i;i=l[i])if(to[i]!=fa)pre_dfs(to[i],p,dep+1);
 9 }
10 void dfs(int p){
11     for(int i=fir[p];i;i=l[i])if(res[to[i]]<res[p]-1)
12         res[to[i]]=res[p]-1,dfs(to[i]);
13 }
14 int main(){
15     scanf("%d%d%d",&n,&k,&t);
16     for(int i=1,x,y;i<n;++i)scanf("%d%d",&x,&y),link(x,y),link(y,x);
17     pre_dfs(1,0,1);
18     while(!q.empty()){
19         int p=q.top().second;q.pop();if(res[p]>=0)continue;
20         for(int i=1;i<=k;++i)if(f[p])p=f[p];
21         res[p]=k;dfs(p);ans++;
22     }
23     printf("%d\n",ans);
24 }

773B的小东西