Cod sursa(job #1709936)

Utilizator lookingForAChallengeUBB Cociorva Popoveniuc Salajan lookingForAChallenge Data 28 mai 2016 14:30:54
Problema Revolta Scor 0
Compilator cpp Status done
Runda ONIS 2016 - Runda - 2 - ACM ICPC Romanian Programming Contest Marime 4.91 kb
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

const int nmax = 100005;
set< pair<int, int> > mySet[nmax];
int dpJos[nmax], dpSus[nmax];
int viz[nmax];
int maxLantInJos[nmax];
vector< int> gf[nmax];
int t[nmax];
int iiFrunza[nmax];
int inSus[nmax];
int n, tt;
set< pair< int, int> > centralSet;
int current[nmax];
int diametruInital;



void reset() {
	for (int i = 1; i <= n; ++i) {
		mySet[i].clear();
		gf[i].clear();
		dpJos[i] = 0;
		dpSus[i] = 0;
		viz[i] = 0;
		inSus[i] = 0;
		maxLantInJos[i] = 0;
		iiFrunza[i] = false;
		current[i] = 0;
	}
	centralSet.clear();
}

void updateSet(int node) {
	if (mySet[node].size() > 3) {
		set< pair< int, int > >::iterator it = mySet[node].begin();
		mySet[node].erase(it);
	}
}

void dfsJos(int node) {
	// dpJos[i] = diametrul maxim din subarobrele lui i
	// mySet[i] = cele mai lungi 3 lanturi in jos;
	viz[node] = 1;
	bool frunza = true;
	for (int i = 0; i < gf[node].size(); ++i) {
		int vc = gf[node][i];
		if (viz[vc] == 0) {
			frunza = false;
			t[vc] = node;
			dfsJos(vc);
		}
	}
	if (frunza) {
		dpJos[node] = 0;
		maxLantInJos[node] = 0;
		iiFrunza[node] = true;
		return;
	}
	for (int i = 0; i < gf[node].size(); ++i) {
		int vc = gf[node][i];
		if (t[vc] == node) {
			// ii fiu;
			int currentMaxLant = maxLantInJos[vc] + 1;
			mySet[node].insert( mp(currentMaxLant, vc) );
			updateSet(node);
			dpJos[node] = max(dpJos[node], dpJos[vc]);
		}
	}
	auto it = mySet[node].end();
	--it;
	maxLantInJos[node] = (*it).first;
	dpJos[node] = max(dpJos[node], maxLantInJos[node]);
	if (mySet[node].size() > 1) {
		--it;
		dpJos[node] = max(dpJos[node], maxLantInJos[node] + (*it).first);
	}
}

void bagaDpJos() {
	dfsJos(1);
}

pair<int, int> getBestSon(int node, int vc) {
	pair<int, int> ans = mp(-1, -1);
	for (auto it : mySet[node]) {
		if (it.second != vc) {
			ans = it;
		}
	}
	return ans;
}

int combineSons(int node, int vc) {
	int max1 = -1;
	int max2 = -1;
	set< pair< int, int> >::iterator  it = mySet[node].end();
	//cerr << node << " " << vc << "  "<< mySet[node].size();
	it--;
	for (; ; --it) {
		if (it->second != vc) {
			if (max1 == -1) {
				max1 = it->first;
			} else {
				max2 = it->first;
				break;
			}
		}
		if (it == mySet[node].begin()) {
			break;
		}
	}
	if (max2 == -1) {
		return max1;
	}
	return max1 + max2;
}

void dfsSus(int node) {
	viz[node] = 1;
	for (int i = 0; i < gf[node].size(); ++i) {
		int vc = gf[node][i];
		if (viz[vc] == 0) {
			inSus[vc] = inSus[node] + 1;
			pair<int, int> ceva = getBestSon(node, vc);
			if (ceva.second != -1) {
				inSus[vc] = max(inSus[vc], ceva.first + 1);
			}
			//dpSus[vc] = max(dpSus[node], inSus[vc]);
			//dpSus[vc] = max(dpSus[node], combineSons(node, vc));
			dfsSus(vc);
		}
	}
}

void bagaDpSus() {
	dfsSus(1);
}

void dfs(int node) {
	viz[node] = 1;
	if (t[node]) {
		// scot muchia node - t[node];
		int diamtruJos = dpJos[node];
		int currentDiamtruSus = max(inSus[t[node]], combineSons(t[node], node));
		pair<int, int> cevaInSus = getBestSon(t[node], node);

		if (cevaInSus.first != -1){
			currentDiamtruSus = max(currentDiamtruSus, inSus[t[node]] + cevaInSus.first);
		}
		if (centralSet.find( mp(current[t[node]], t[node]) ) != centralSet.end() ) {
			centralSet.erase(centralSet.find( mp(current[t[node]], t[node]) ));
		}
		centralSet.insert(mp(currentDiamtruSus, t[node]));
		current[ t[node] ] = currentDiamtruSus;
		set< pair< int, int> > ::iterator it = centralSet.end();
		--it;
		int diametruSus = it->first;
		int newDiameter = (diamtruJos+1) / 2 + (diametruSus+1) / 2 + 1;
		newDiameter = max(newDiameter, diamtruJos);
		newDiameter = max(newDiameter, diametruSus);
		diametruInital = min(diametruInital, newDiameter);
		// for(auto ceva : centralSet){
		// 	cout << ceva.first << "  "<< ceva.second << "\n";
		// }
		// cout << t[node] << " -> " << node << " " << diamtruJos << " " << diametruSus << "\n";
	}
	for(int i=0; i<gf[node].size(); ++i){
		int vc = gf[node][i];
		if (viz[vc] == 0){
			dfs(vc);
		}
	}
	if (centralSet.find( mp(current[node], node )) != centralSet.end() )
		centralSet.erase( centralSet.find( mp(current[node], node )) );
}

int main() {
	cin.sync_with_stdio(false);
	freopen("revolta.in", "r", stdin);
	freopen("revolta.out", "w", stdout);

	cin >> tt;
	for (; tt; --tt) {
		cin >> n;
		reset();
		for (int i = 1; i < n; ++i) {
			int x, y;
			cin >> x >> y;
			/// nu uita inanite sa trimitiii!!!!!!
			++x; ++y;
			gf[x].pb(y);
			gf[y].pb(x);
		}
		bagaDpJos();
		diametruInital = dpJos[1];
		for (int i = 1; i <= n; ++i) {
			viz[i] = 0;
		}
		bagaDpSus();
		// for (int i = 1; i <= n; ++i) {
		// 	cout << i << " " << dpJos[i] << "\n";
		// }
		// for (int i = 1; i <= n; ++i) {
		// 	cout << i << " " << inSus[i] << "\n";
		// }
		for (int i = 1; i <= n; ++i) {
			viz[i] = 0;
		}

		dfs(1);
		cout << diametruInital << "\n";
	}


	return 0;
}