题意:

给你一棵 n (n<=300000) 个点的树，请删一些点使得树的直径小于等于 k (k<=n)  问最少删多少点

我们考虑去枚举哪一个点/边为新树的直径的中间的位置。用树分治求解。

当 k 为偶数时

我们每次对 root 进行计算时都要对位于子树 u 内的节点 x 计算其他子树中的点对 x 的贡献，统计出与x距离大于k/2的点且不在子树u内的点有多少个 

同时还要计算到root距离大于 k/2 的点有多少

当 k 为奇数时

我们每次对 root 进行计算时都要对位于子树 u 内的节点 x 的返祖边计算其他子树中的点对这条边的贡献，统计出与x距离大于k/2-deep[x]+1的点且不在子树u内的点有多少个

当这条边是x与root之间的边时，还要计算一下子树 u 内的点对这条边的贡献。

  1 #include<iostream>
  2 #include<cstdlib>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<algorithm>
  7 #define N 300005
  8 using namespace std;
  9 int T,n,K;
 10 int zz,a[N];
 11 struct ro{
 12     int to,next;
 13 }road[N*2];
 14 void build(int x,int y)
 15 {
 16     zz++;
 17     road[zz].to=y;
 18     road[zz].next=a[x];
 19     a[x]=zz;
 20 }
 21 int size[N];
 22 bool vis[N];
 23 int f[N],sum,root;
 24 void find_root(int x,int fa)
 25 {
 26     size[x]=1;
 27     f[x]=0;
 28     for(int i=a[x];i;i=road[i].next)
 29     {
 30         int y=road[i].to;
 31         if(y==fa||vis[y]) continue;
 32         find_root(y,x);
 33         if(size[y]>f[x]) f[x]=size[y];
 34         size[x]+=size[y];
 35     }
 36     if(sum-size[x]>f[x]) f[x]=sum-size[x];
 37     if(f[x]<f[root]) root=x;
 38 }
 39 int cnt[N],cnt1[N],sm[N];
 40 int mx,mx1;
 41 void dfs(int x,int sum,int fa)
 42 {
 43     cnt[sum]++;
 44     mx=max(mx,sum);
 45     for(int i=a[x];i;i=road[i].next)
 46     {
 47         int y=road[i].to;
 48         if(y==fa||vis[y])continue;
 49         dfs(y,sum+1,x);
 50     }
 51 }
 52 void dfs2(int x,int sum,int fa)
 53 {
 54     cnt1[sum]++;
 55     mx1=max(mx1,sum);
 56     for(int i=a[x];i;i=road[i].next)
 57     {
 58         int y=road[i].to;
 59         if(y==fa||vis[y])continue;
 60         dfs2(y,sum+1,x);
 61     }
 62 }
 63 void dfs3(int x,int sum,int fa,int fr)
 64 {
 65     if(!(K&1))
 66     {
 67         if(sum<=K/2+1) sm[x]+=cnt[K/2+1-sum]-cnt1[K/2+1-sum];
 68         else sm[x]+=cnt[0]-cnt1[0];
 69 //        if(x==1) cout<<x<<' '<<root<<' '<<sm[x]<<endl;
 70     }
 71     else
 72     {
 73         if(K/2-sum+2>=0) sm[fr]+=cnt[K/2-sum+2]-cnt1[K/2-sum+2];
 74         else sm[fr]+=cnt[0]-cnt1[0];
 75         if(fa==root)
 76         {
 77             sm[fr]+=cnt1[K/2+sum+1];
 78         }
 79     }
 80     for(int i=a[x];i;i=road[i].next)
 81     {
 82         int y=road[i].to;
 83         if(y==fa||vis[y])continue;
 84         dfs3(y,sum+1,x,i/2);
 85     }
 86 }
 87 void solve(int x)
 88 {
 89     vis[x]=1;
 90     mx=0;
 91     cnt[0]=1;
 92     for(int i=a[x];i;i=road[i].next)
 93     {
 94         int y=road[i].to;
 95         if(vis[y]) continue;
 96         dfs(y,1,x);
 97         
 98     }
 99     for(int i=mx-1;i>=0;i--) cnt[i]+=cnt[i+1];
100     if(!(K&1)) sm[x]+=cnt[K/2+1];
101 //    if(x==1) cout<<x<<' '<<root<<' '<<sm[x]<<endl;
102     for(int i=a[x];i;i=road[i].next)
103     {
104         int y=road[i].to;
105         if(vis[y])continue; 
106         mx1=0;
107         dfs2(y,1,x);
108         for(int j=mx1-1;j>=0;j--) cnt1[j]+=cnt1[j+1];
109         dfs3(y,1,x,i/2);
110         for(int j=mx1;j>=0;j--) cnt1[j]=0;
111         mx1=0;
112     }
113     for(int i=mx;i>=0;i--) cnt[i]=0;
114     for(int i=a[x];i;i=road[i].next)
115     {
116         int y=road[i].to;
117         if(vis[y]) continue;
118         root=0;
119         sum=size[y];
120         find_root(y,x);
121         solve(root);
122     }
123 }
124 int main()
125 {
126     scanf("%d",&T);
127     while(T--)
128     {
129         scanf("%d%d",&n,&K);
130         zz=1;
131         memset(vis,0,sizeof(vis));
132         memset(a,0,sizeof(a));
133         memset(f,0,sizeof(f));
134         memset(sm,0,sizeof(sm));
135         memset(cnt,0,sizeof(cnt));
136         memset(size,0,sizeof(size));
137         root=0;
138         for(int i=1;i<n;i++)
139         {
140             int x,y;
141             scanf("%d%d",&x,&y);
142             build(x,y);
143             build(y,x);
144         }
145         f[0]=0x7fffffff;
146         root=0;
147         sum=n;
148         find_root(1,0);
149         solve(root);
150         int ans=0x7fffffff;
151         if(K&1)
152         {
153             for(int i=1;i<n;i++)
154             {
155                 ans=min(ans,sm[i]);    
156             }
157         }
158         else
159         {
160             for(int i=1;i<=n;i++)
161             {
162                 ans=min(ans,sm[i]);    
163             }
164         }
165         
166         printf("%d\n",ans);
167     }
168     return 0; 
169 } 
170 /*
171 2
172 10 3
173 1 2
174 1 3
175 2 4
176 2 5
177 3 6
178 3 7
179 4 8
180 4 9
181 5 10
182 
183 10 3
184 1 2
185 1 3
186 2 4
187 2 5
188 3 6
189 3 7
190 4 8
191 4 9
192 5 10
193 
194 */

View Code