2023营业执照年检入口官网,四川seo关键词工具,建筑公司网站应该则么做,营销助手下载app下载F.孤独#xff08;牛客小白月赛39#xff09;
题意#xff1a;
给定一棵树#xff0c;寻找一个路径#xff0c;将断掉所有与这个路径上的点相连的边#xff0c;使得剩下的最大连通块的大小最小
题解#xff1a;
这题有点印象#xff0c;感觉做过#xff0c;至少这…F.孤独牛客小白月赛39
题意
给定一棵树寻找一个路径将断掉所有与这个路径上的点相连的边使得剩下的最大连通块的大小最小
题解
这题有点印象感觉做过至少这个方法肯定遇到过 设dp[u]表示以u为根的子树里删除以u为起点的路径后最大连通块的大小最小是多少 我们贪心的去进行转移它一定是选择最大儿子去走路径去删除因为只有这样才会影响到最大连通块(最大儿子意味着最大连通块)
所以转移方程为dp[u]max(sz[v2],dp[v1]),最大连通块要么是以v1为根删除得到的最大连通块要么就是子树v2 但是这个dp[i]并不是答案 因为路径并不是只从u开始有可能路径的两端都在一个子树里 此时路径一定是以u为根的子树里因为有两个方向的路径因此一定走最大儿子和次大儿子。此时连通块有这几部分以v1为根的子树里删除后剩下的连通块以v2为根的子树里删除后剩下的连通块第三大叶子节点v3还有就是除了以u为根的子树之外所有点组成一个连通块这四部分取max答案我们取min 此时答案就是ansmin(ans,max(n-sz[u],dp[v1],dp[v2],sz[v3]))
代码
#include bits/stdc.h
using namespace std;
const int maxn3e6;
vectorint v[maxn];
int n;
int dp[maxn];
int sz[maxn];
int res 1e9;
void dfs(int u, int fa)
{sz[u] 1;dp[u] 1;int maxv 0;int maxv2 0;int maxv3 0;int id 0; //大儿子int id2 0; //次大儿子for (auto j : v[u]) {if (j fa)continue;dfs(j, u);sz[u] sz[j];if (sz[j] maxv) {maxv3 maxv2;maxv2 maxv;maxv sz[j];id2 id;id j;}else if (sz[j] maxv2) {id2 j;maxv3 maxv2;maxv2 sz[j];}else if (sz[j] maxv3) {maxv3 sz[j];}}int ans 0;dp[u] max(maxv2, dp[id]);res min(res, max({n - sz[u], maxv3, dp[id], dp[id2]}));
}
int main()
{cin n;for (int i 0; i n - 1; i) {int a, b;scanf(%d%d, a, b);v[a].push_back(b);v[b].push_back(a);}dfs(1, 0);cout res endl;return 0;
}
