|
题意: 给你一棵 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
来源：https://www./content-4-731801.html |
|
|
