Cod sursa(job #1709634)

Utilizator cojocarugabiReality cojocarugabi Data 28 mai 2016 13:09:13
Problema Revolta Scor 0
Compilator cpp Status done
Runda ONIS 2016 - Runda - 2 - ACM ICPC Romanian Programming Contest Marime 1.65 kb
# include <bits/stdc++.h>
using namespace std;
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define db long double
# define scn(x) scanf("%I64d",&x)
# define scan(x) scanf("%d",&x)
# define print(x) printf("%d ",x)
# define prnt(x) printf("%I64d ",x);
# define eol printf("\n")
# define IOS ios_base :: sync_with_stdio(0)
# define pe "Possible"
# define ie "Impossible"
# define halt(...) {fo << (__VA_ARGS__) << '\n';exit(0);}
# define rep(n) for (int qwerty = 1;qwerty <= n;++qwerty)
# define pp(n) cerr << #n << " = " << n << '\n'
# define ppp(v) for (auto it : v) cerr << it << ' ';cerr << '\n'
const int mod = 1e9 + 7;
vector < int > s[1 << 20];
int d[1 << 20];
void dfs(int node,int prev)
{
    d[node] = d[prev] + 1;
    for (auto it : s[node])
        if (it != prev)
            dfs(it,node);
}
int main(void)
{
    int t;
    freopen("revolta.in","r",stdin);
    ofstream fo("revolta.out");
    scan(t);
    while (t --)
    {
        int n;
        scan(n);
        for (int i = 1;i < n;++i)
        {
            int a,b;
            scan(a);scan(b);
            ++a;++b;
            s[a].push_back(b);
            s[b].push_back(a);
        }
        for (int i = 0;i <= n;++i) d[i] = 0;
        dfs(1,0);
        int mx = *max_element(d+1,d+1+n);--mx;
        int node = *max_element(d+1,d+1+n);
        dfs(node,0);
        int Max = *max_element(d+1,d+1+n);
        int all = 0;
        for (int i = 1;i <= n;++i) all += d[i] == Max;
        fo << max(1,all == 1 ? mx - 1 : mx) << '\n';
        for (int i = 1;i <= n;++i) s[i].clear();
    }
    return 0;
}