企业官网建设流程全解析

视频讲解：[GESP202512 六级] 分树规划-信息学奥赛GESP等级考试真题解析

一、原题

题目描述

老师有一棵有 n 个结点的树，结点依次以 1,2,…,n 编号。

老师想将这棵树作为奖品分给两位同学。具体而言，老师会选择一条边并从树上删去它，从而将这棵树分为两个连通块。两位同学分别可以得到其中一个连通块。

如果有同学拿到的连通块结点数明显小于另一位同学，那么这位同学会不太高兴。为了避免这种情况出现，老师想知道两个连通块结点数之差的绝对值最小是多少。

输入格式

第一行，一个正整数 n，表示结点数量。

接下来 n−1 行，每行两个正整数 ui​,vi​，表示一条连接结点 ui​ 和结点 vi​ 的边。

输出格式

输出一行，一个整数，表示答案。

输入输出样例

输入 #1

4 1 2 2 3 3 4

输出 #1

0

输入 #2

6 1 2 1 3 1 4 1 5 5 6

输出 #2

2

说明/提示

对于 40% 的测试点，保证 2≤n≤500。

对于所有测试点，保证 2≤n≤2×10^4。

二、做题思路

1)邻接表构造树

#include<bits/stdc++.h> using namespace std; int n; map<int,vector<int>>g; int main(){ //1)邻接表构造树 //1.1)确定结点数量 cin>>n; //1.2)填充n-1条边的 for(int i=1;i<=n-1;i++){ int u,v;cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } }

2)深搜计算每个结点的结点数量(包括自身)

#include<bits/stdc++.h> using namespace std; int n; map<int,vector<int>>g; bool vis[20004]; int c[20004]; //2)深搜函数 :计算每个结点的结点数(包括自身) void dfs(int x){ //2.1)标记访问 vis[x]=1; //2.2)搜索每个子节点 for(auto it:g[x]){ if(vis[it]==0){ dfs(it); //2.3)累加当前子节点数 c[x]+=c[it]; } } //2.4)自身也算 c[x]++; } int main(){ //1)邻接表构造树 //.... //2)深搜计算每个结点的结点数(包括自身) dfs(1); }

3)找每条边，左右结点数之差的绝对值最小

#include<bits/stdc++.h> using namespace std; int ans=INT_MAX; void dfs(int x){ //... //3)找每条边，左右结点数之差的绝对值最小 ans=min(ans, abs(c[x]-(n-c[x])) ); } int main(){ //... cout<<ans; }

三、答案

#include<bits/stdc++.h> using namespace std; int n; map<int,vector<int>>g; bool vis[20004]; int c[20004]; int ans=INT_MAX; //2)深搜函数 :计算每个结点的结点数(包括自身) void dfs(int x){ //2.1)标记访问 vis[x]=1; //2.2)搜索每个子节点 for(auto it:g[x]){ if(vis[it]==0){ dfs(it); //2.3)累加当前子节点数 c[x]+=c[it]; } } //2.4)自身也算 c[x]++; //3)找每条边，左右结点数之差的绝对值最小 ans=min(ans, abs(c[x]-(n-c[x])) ); } int main(){ //1)邻接表构造树 //1.1)确定结点数量 cin>>n; //1.2)填充n-1条边的 for(int i=1;i<=n-1;i++){ int u,v;cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } //2)深搜计算每个结点的结点数(包括自身) dfs(1); cout<<ans; }