Cod sursa(job #732674)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 10 aprilie 2012 19:41:04
Problema Cerere Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <cstdio>
#include <vector>

#define Infinity 1000000000000LL
#define NMax 200005
#define LL long long
#define Buff 10000000

using namespace std;

vector <int> G[NMax];
int N, Size[NMax], C;
LL DSum[NMax], USum[NMax], CSum;
char Buffer[Buff]; int BuffI;

inline int ReadX()
{
    int X=0;
    while(!(Buffer[BuffI]>='0' && Buffer[BuffI]<='9'))
    {
        ++BuffI;
    }
    while(Buffer[BuffI]>='0' && Buffer[BuffI]<='9')
    {
        X=X*10+Buffer[BuffI]-'0';
        ++BuffI;
    }
    return X;
}

void Read ()
{
    freopen ("capitala.in", "r", stdin);
    fread (Buffer, 1, Buff, stdin);
    N=ReadX ();
    for (int i=1; i<N; ++i)
    {
        int X=ReadX (), Y=ReadX ();
        G[X].push_back (Y); G[Y].push_back (X);
    }
}

void Print ()
{
    freopen ("capitala.out", "w", stdout);
    printf ("%d %lld\n", C, CSum);
}

inline void DownDFS (int X, int F)
{
    Size[X]=1;
    for (vector <int> :: iterator Y=G[X].begin (); Y!=G[X].end (); ++Y)
    {
        if (*Y==F) continue;
        DownDFS (*Y, X);
        Size[X]+=Size[*Y]; DSum[X]+=(DSum[*Y]+Size[*Y]);
    }
}

inline void UpDFS (int X, int F)
{
    USum[X]=USum[F]+DSum[F]-(DSum[X]+Size[X])+Size[1]-Size[X];
    for (vector <int> :: iterator Y=G[X].begin (); Y!=G[X].end (); ++Y)
    {
        if (*Y==F) continue;
        UpDFS (*Y, X);
    }
}

void Solve ()
{
    DownDFS (1, 0);
    DSum[0]=DSum[1]+Size[1];
    UpDFS (1, 0);
    CSum=Infinity;
    for (int X=1; X<=N; ++X)
    {
        if (DSum[X]+USum[X]<CSum)
        {
            CSum=DSum[X]+USum[X]; C=X;
        }
    }
}

int main()
{
    Read ();
    Solve ();
    Print ();
    return 0;
}