Submission #851390

#	Time	Username	Problem	Language	Result	Execution time	Memory
851390		vjudge1	Papričice (COCI20_papricice)	C++98	0 / 110	5 ms	17496 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
#define int long long
#define vi vector<int>
#define pb push_back
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
const int N = 2e5+1;

vi sz(N),best(N),edges[N];
set<int> sts[N];

int getsz(int node,int parent) {
	int ans = 1;
	for (auto nb : edges[node]) {
		if (nb != parent) ans+=getsz(nb,node);
	}
	return sz[node] = ans;
}

void setswap(int node,int parent) {
	double targ = sz[node]/2.0;
	//cout << "Node " << node sp targ << endl;
	int c = abs(targ-sz[node]);
	int d = sz[node];
	sts[node].insert(sz[node]);
	for (auto nb : edges[node]) {
		if (nb==parent) continue;
		setswap(nb,node);
		if (nb != parent) {
			if (sts[nb].size() > sts[node].size()) swap(sts[nb],sts[node]);
			for (auto it : sts[nb]) sts[node].insert(it);
		}
	}
	for (auto it : sts[node]) {
		if (abs(targ-it) < c) {
			c = abs(targ-it);
			d = it;
		}
	}
	best[node] = d;
}


void solve() {
	int n;
	cin >> n;
	for (int i=1;i<=n-1;i++) {
		int a,b;
		cin >> a >> b;
		edges[a].pb(b);
		edges[b].pb(a);
	}
	getsz(1,1);
	setswap(1,1);
	int ans = 1e18;
	for (int i=1;i<=n;i++) {
		int haha1 = n-sz[i];
		int haha2 = sz[i]-best[i];
		int haha3 = best[i];
		ans = min(ans,max({haha1,haha2,haha3})-min({haha1,haha2,haha3}));
	}
	cout << ans << endl;
}    
 
 
 
                                
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}
 
 
 

• Subtask 1: 0 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 60