Pagini recente » Cod sursa (job #1176720) | Cod sursa (job #2819314) | Cod sursa (job #3221256) | Clasament cerculdeinfo-lectia8-kmp_z_manacher | Cod sursa (job #732674)
Cod sursa(job #732674)
#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;
}