Pagini recente » Cerc3 | ONIS 2014, Clasament | infasuratoare | Profil caheman | Cod sursa (job #1710244)
#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]-1 << " -> " << node-1 << " in jos " << diamtruJos << " in sus " << 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;
}