Pagini recente » Cod sursa (job #2507995) | Cod sursa (job #588088) | Cod sursa (job #2506071) | Cod sursa (job #1783538) | Cod sursa (job #919392)
Cod sursa(job #919392)
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define NMAX 2100
#define max(a, b) ((a) > (b) ? (a) : (b))
int i, j, k, p, q, N, wincnt;
int visited[NMAX], tata[NMAX], special[NMAX], lmax[NMAX], path[NMAX], pathmax[NMAX];
char win[NMAX][NMAX];
vector<int> v[NMAX];
void df1(int x)
{
int j;
visited[x] = 1;
for (j = 0; j < v[x].size(); j++)
if (!visited[v[x][j]])
{
tata[v[x][j]] = x;
df1(v[x][j]);
}
}
void df2(int x)
{
int j;
visited[x] = 1;
for (j = 0; j < v[x].size(); j++)
if (!visited[v[x][j]] && ! special[v[x][j]])
{
df2(v[x][j]);
lmax[x] = max(lmax[x], 1 + lmax[v[x][j]]);
}
}
void n3sol(void)
{
int a, b;
wincnt = 0;
for (a = 1; a <= N; a++)
for (b = 1; b <= N; b++)
if (a != b)
{
memset(visited, 0, sizeof(visited));
memset(tata, 0, sizeof(tata));
df1(a);
memset(special, 0, sizeof(special));
p = b;
q = 0;
do
{
special[p] = 1;
q++;
path[q] = p;
p = tata[p];
}
while (p > 0);
memset(visited, 0, sizeof(visited));
memset(lmax, 0, sizeof(lmax));
for (p = q; p >= 1; p--)
df2(path[p]);
pathmax[0] = 0;
for (p = 1; p <= q; p++)
pathmax[p] = max(pathmax[p - 1], lmax[path[p]] + p - 1);
win[a][b] = 0;
for (p = q; p >= 1 + (q / 2); p--)
if (lmax[path[p]] + q - p > pathmax[/*q / 2*/ p - 1])
{
win[a][b] = 1;
break;
}
// fprintf(stderr, "a=%d, b=%d => %d\n", a, b, win[a][b]);
if (win[a][b])
wincnt++;
}
}
int main()
{
freopen("trigame.in", "r", stdin);
scanf("%d", &N);
for (k = 1; k <= N - 1; k++)
{
scanf("%d %d", &i, &j);
v[i].push_back(j);
v[j].push_back(i);
}
n3sol();
freopen("trigame.out", "w", stdout);
printf("%d\n", wincnt);
return 0;
}