题意： 给定一颗无向无根树，求一大小为K的联通子图使得非子图最远点距离子图距离最小
树， 且联通
考虑平均砍去部分子树使得答案最优即可
所以从叶子入手一层一层往里砍， 砍几层答案是几
那么需要记录信息 p[y] 为以 y 为根的子树最大深度为多少
所以要找个根，当树的中心为根时 p[y]最平均
所以两遍dfs求树中心即可
用树中心树上dp子树最大深度，
按深度遍历累加 当累加树达到时直接输出就完了。
如图 留3个时 ，树中心为1，红圈里的答案最优。
代码
/*
Zeolim - An AC a day keeps the bug away
*/
//pragma GCC optimize(2)
//#pragma GCC ("-W1,--stack=128000000")
#include <bits/stdc++.h>
using namespace std;
#define mp(x, y) make_pair(x, y)
#define fr(x, y, z) for(int x = y; x < z; ++x)
typedef long long ll;
typedef double ld;
typedef std::pair<int, int> pii;
typedef std::vector <int> vi;
//typedef __int128 ill;
const ld PI = acos(-1.0);
const ld E = exp(1.0);
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9 + 7;
const int MAXN = 1e6 + 10;
vector <int> edge[MAXN];
int n, k;
int p[MAXN] = {0}, cnt[MAXN] = {0}, in[MAXN] = {0};
int lst = -1, lstlen = -1, rot = -1;
bitset <MAXN> used;
void dfs(int now, int step)
{
used[now] = true;
if(step > lstlen)
lstlen = step, lst = now;
for(auto x : edge[now])
{
if(!used[x])
dfs(x, step + 1);
}
used[now] = false;
}
void gao1(int now, int step)
{
used[now] = true;
p[step] = now;
if(step > lstlen)
lstlen = step, lst = now, rot = p[step / 2];
for(auto x : edge[now])
{
if(!used[x])
gao1(x, step + 1);
}
used[now] = false;
}
void xiagao(int now, int fa)
{
used[now] = true;
for(auto x : edge[now])
{
if(!used[x])
xiagao(x, now);
}
p[fa] = max(p[fa], p[now] + 1);
used[now] = false;
}
void gao()
{
used.reset();
dfs(1, 0);
used.reset();
int nb = lst;
lst = lstlen = -1;
gao1(nb, 0);
fill(p, p + n + 10, 1);
used.reset();
xiagao(rot, 0);
for(int i = 1; i <= n; ++i)
++cnt[p[i]];
int sum = 0;
for(int i = 1; i <= n; ++i)
{
sum += cnt[i];
if(sum >= n - k)
{
cout << i << '
';
return ;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen("d:out.txt","w",stdout);
//freopen("in.txt","r",stdin);
cin >> n >> k;
for(int i = 1, x, y; i < n; ++i)
{
cin >> x >> y;
edge[x].push_back(y);
++in[x], ++in[y];
edge[y].push_back(x);
}
gao();
return 0;
}
/*
6 1
1 2
2 3
2 4
1 5
5 6
*/后来发现求p也不用那么麻烦找中心，
可以用拓扑从叶子入手一层一层进行dp求p数组
这样也是均匀的
其他一样
/*
Zeolim - An AC a day keeps the bug away
*/
//pragma GCC optimize(2)
//#pragma GCC ("-W1,--stack=128000000")
#include <bits/stdc++.h>
using namespace std;
#define mp(x, y) make_pair(x, y)
#define fr(x, y, z) for(int x = y; x < z; ++x)
typedef long long ll;
typedef double ld;
typedef std::pair<int, int> pii;
typedef std::vector <int> vi;
//typedef __int128 ill;
const ld PI = acos(-1.0);
const ld E = exp(1.0);
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9 + 7;
const int MAXN = 1e6 + 10;
vector <int> edge[MAXN];
int n, k;
int p[MAXN] = {0}, cnt[MAXN] = {0}, in[MAXN] = {0};
void gao()
{
queue <int> Q;
for(int i = 1; i <= n; ++i)
{
if(in[i] == 1)
Q.push(i), p[i] = 1;
}
while(!Q.empty())
{
int now = Q.front();
Q.pop();
for(auto x : edge[now])
{
if(in[x] == 1) continue; //已经算过的叶子要直接跳过 不然影响p数组更新
p[x] = max(p[x], p[now] + 1);
if(--in[x] == 1) //无向图 入度为 1 即为叶子
Q.push(x);
}
}
for(int i = 1; i <= n; ++i)
++cnt[p[i]];
int sum = 0;
for(int i = 1; i <= n; ++i)
{
sum += cnt[i];
if(sum >= n - k)
{
cout << i << '
';
return ;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen("d:out.txt","w",stdout);
//freopen("in.txt","r",stdin);
cin >> n >> k;
for(int i = 1, x, y; i < n; ++i)
{
cin >> x >> y;
edge[x].push_back(y);
++in[x], ++in[y];
edge[y].push_back(x);
}
gao();
return 0;
}
/*
6 1
1 2
2 3
2 4
1 5
5 6
*/