Pagini recente » Cod sursa (job #2200920) | Cod sursa (job #3294325) | Cod sursa (job #2048948) | Cod sursa (job #1448181) | Cod sursa (job #2051812)
#include <bits/stdc++.h>
#define maxN 2050
using namespace std;
FILE *fin = freopen("trigrame.in", "r", stdin);
FILE *fout = freopen("trigrame.out", "w", stdout);
/* ---------------------------------- */
int n;
vector < int > V[maxN];
/* ---------------------------------- */
int f[maxN], lev[maxN], down[2][maxN], maxDown[maxN];
bool vis[maxN][maxN], dp[maxN][maxN];
int ans;
void dfs1(int nod)
{
down[0][nod] = down[1][nod] = 1;
for (int son : V[nod])
if (!f[son])
{
f[son] = nod;
lev[son] = lev[nod] + 1;
dfs1(son);
if (down[0][son] + 1 > down[0][nod])
{
down[1][nod] = down[0][nod];
down[0][nod] = down[0][son] + 1;
}
else
down[1][nod] = max(down[1][nod], down[0][son] + 1);
}
}
void dfs2(int nod)
{
int bestNod;
for (int son : V[nod])
if (f[son] == 1)
{
maxDown[son] = maxDown[nod] + 1;
if (down[0][nod] == down[0][son] + 1)
{
maxDown[son] = max(maxDown[son], down[1][nod] + 1);
bestNod = down[1][nod];
}
else
{
maxDown[son] = max(maxDown[son], down[0][nod] + 1);
bestNod = down[0][nod];
}
bestNod = max(bestNod, maxDown[nod]);
vis[nod][son] = vis[son][nod] = 1;
if (down[0][son] < bestNod)
{
dp[nod][son] = 1;
dp[son][nod] = 0;
}
else if (down[0][son] > bestNod)
{
dp[nod][son] = 0;
dp[son][nod] = 1;
}
else
dp[nod][son] = dp[son][nod] = 0;
}
}
int Dp(int x, int y)
{
if (vis[x][y])
return dp[x][y];
vis[x][y] = 1;
for (int z : V[x])
if (z != y)
{
if (!vis[y][z])
dp[y][z] = Dp(y, z);
if (!dp[y][z])
{
dp[x][y] = 1;
vis[y][x] = 1;
dp[y][x] = 0;
return 1;
}
}
dp[x][y] = 0;
return 0;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
{
int x, y;
scanf("%d %d", &x, &y);
V[x].push_back(y);
V[y].push_back(x);
}
f[1] = -1;
dfs1(1);
maxDown[1] = 1;
dfs2(1);
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
if (j != i)
{
if (!vis[i][j])
dp[i][j] = Dp(i, j);
ans += dp[i][j];
// if (dp[i][j])
// printf("%d %d\n", i, j);
}
printf("%d\n", ans);
return 0;
}