企业手机网站建设有,百度seo关键词排名s,镇江百度网站建设,网站图片验证码出不来D. A Wide, Wide Graph
题目#xff1a;
思路#xff1a; 考察树的直径的性质以及逆向思维 这一题要是正向思考可能会有些难#xff0c;我们不如反向思考看看
树上的最长路线是树的直径#xff0c;也就是说如果 k 大于了直径 d#xff0c;那么所有点都将是一个联通块
思路 考察树的直径的性质以及逆向思维 这一题要是正向思考可能会有些难我们不如反向思考看看
树上的最长路线是树的直径也就是说如果 k 大于了直径 d那么所有点都将是一个联通块否则肯定会有点连接起来
如果我们知道树的直径的性质那么这题就迎刃而解了
对于树的直径的两个端点 u,v树上任意一点 z 的最长路径其终点一定在 u 或者 v 上
那么只要知道了这个我们就好做了既然要满足两点间的距离大于等于 k那么肯定是取最大值看由于最大值一定会连接到直径两端任意一个那么只要 z 对于 u,v 两点的距离大于等于 k那么就会和 u,v 一起变成一个连通块并且最后的形态肯定是 一个连通块 和 x 个单点
为什么呢感性的想既然 z 到 u,v 的距离最大那么肯定是先连 u,v如果有别的节点 y那么肯定会一起到 u,v 中即不可能存在先连接 y 再连接 u,v 的情况
所以我们可以用三次dfs来解决这题前两次求直径的两个端点同时求每个节点到端点 1 的距离第三次我们求所有点到端点 2 的距离最后模拟即可
代码
#include iostream
#include algorithm
#includecstring
#includecctype
#includestring
#include set
#include vector
#include cmath
#include queue
#include unordered_set
#include map
#include unordered_map
#include stack
#include memory
using namespace std;
#define int long long
#define yes cout Yes\n
#define no cout No\nvoid solve()
{int n;cin n;vectorvectorint g(n 1);for (int i 0; i n-1; i){int u, v;cin u v;g[u].push_back(v);g[v].push_back(u);}vectorint dep(n 1, 0),dep2(n1,0),dep3(n1,0);int root1 0, root2 0;auto dfs1 [](auto self, int fa, int se) -void {dep[se] dep[fa] 1;for (auto son : g[se]){if (son fa) continue;self(self, se, son);}if (dep[se] dep[root1]){root1 se;}};dfs1(dfs1, 1, 1);auto dfs2 [](auto self, int fa, int se) -void {dep2[se] dep2[fa] 1;for (auto son : g[se]){if (son fa) continue;self(self, se, son);}if (dep2[se] dep2[root2]){root2 se;}};dfs2(dfs2, root1, root1);auto dfs3 [](auto self, int fa, int se) -void {dep3[se] dep3[fa] 1;for (auto son : g[se]){if (son fa) continue;self(self, se, son);}};dfs3(dfs3, root2, root2);vectorint dis(n 1, -1e9);for (int i 1; i n; i){dis[i] max(dep2[i], dep3[i]) - 1;}sort(dis.begin(), dis.end());vectorint ans;int index n;int nowans n;int k n;int flag 0;while (k0){while (index 0 dis[index] k){index--;nowans--;flag 1;}ans.push_back(nowans flag);k--;}for (int i n-1; i 0; i--){cout ans[i] ;}cout endl;
}signed main()
{cin.tie(0)-sync_with_stdio(false);int t 1;while (t--){solve();}return 0;
}
