WA了6个点,快疯了
  • 板块P1395 会议
  • 楼主www159
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/4/4 09:15
  • 上次更新2023/11/5 01:04:24
查看原帖
WA了6个点,快疯了
96320
www159楼主2021/4/4 09:15
#include<iostream>
#include<cstdio>
using namespace std;
int rd(){
	int x = 0;
	char s = getchar();
	while(s < '0' || s > '9'){
		s = getchar();
	}
	while(s <= '9' && s >= '0'){
		x = (x<<1)+(x<<3)+(s^48);
		s = getchar();
	}
	return x;
}
#define rd rd()

const int maxn = 1e6+4, inf = 0x3f3f3f3f;
int size[maxn], mins, minn;
int dep[maxn], totdis;
int n;
int to[maxn], nxt[maxn], head[maxn], cnt;

void add(int u, int v){
	cnt++;
	nxt[cnt] = head[u];
	head[u] = cnt;
	to[cnt] = v;
}


void dfs(int u, int f){
	int maxs = 0;
	size[u] = 1;
	for(int p = head[u]; p; p = nxt[p]){
		int v = to[p];
		if(v != f){
			dfs(v, u);
			size[u] += size[v];
			maxs = max(maxs, size[v]);
		}
		maxs = max(maxs, n-size[u]);
		if(maxs < mins || (maxs == mins && u < minn)){
			mins = maxs;
			minn = u;
		}
	}
}

void dfs2(int u, int f){
	dep[u] = dep[f] + 1;
	totdis += dep[u];
	for(int p = head[u]; p; p = nxt[p]){
		int v = to[p];
		if(v != f){
			dfs2(v, u);
		}
	}
}

int main(){
	n = rd;
	int u, v;
	for(int i = 1; i < n; i++){
		u = rd;
		v = rd;
		add(u, v);
		add(v, u);
	}
	
	mins = inf;
	dfs(1, 0);
	dep[0] = -1;
	dfs2(minn, 0);
	cout<<minn<<" "<<totdis;
	return 0;
}
2021/4/4 09:15
加载中...