AcWing 846. 树的重心（DFS）

题目链接

https://www.acwing.com/problem/content/848/

思路

思路大概是，我们对树上的每个点去算一下它的所有子树的情况，然后再和去除以当前节点为根的子树就是剩下的连通块的大小了，然后我们用一个res值记录这个连通块的大小，然后全局定义一个ans，初始化为比较大的数，然后每次搜到一个点，那么我们就更新一下最大连通块的最小值即可，详情请看代码，建图是使用的链式前向星

代码

#include
using namespace std;
//----------------自定义部分----------------
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair

int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};

ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;
//----------------自定义部分----------------
int n,m,q,a[N],h[N],e[N],ne[N],idx;

bool vis[N];

void add(int u,int v){
	e[idx] = v;
	ne[idx] = h[u];
	h[u]=idx++;
}
int ans = 0x3f3f3f3f;
//DFS返回的是以u为根的数的节点个数
int dfs(int u){
	vis[u] = true;//如果被访问过那么就不访问了
	int sum = 1,res = 0;//sum表示的是以u为根的子树中的节点总数
	//res表示的是u的儿子节点的子树的节点个数
	for(int i = h[u]; ~i ;i = ne[i]){//遍历u的所有儿子子树
		int j = e[i];
		if(!vis[j]){
			int k = dfs(j);
			res = max(res,k);//找到儿子子树节点个数的最大值
			sum += k;//加上每个儿子子树的节点
		}
	}
	res = max(res,n-sum);//然后与u的父节点的其他子树和取个最大值
	ans = min(ans,res);//将最大值最小化
	return sum;//返回当前u为根的子树节点数
}


int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	
	cin>>n;
	memset(h,-1,sizeof h);
	int u,v;
	for(int i = 1;i >u>>v;
		add(u,v),add(v,u);
	}
	
	dfs(1);
	
	cout