[PA 2001] Inwestycja

[Dumel]

zrobiłem sobie takie oto zadanko: ... con=PA2001 ale dostałem za nie tylko 90/100 pkt. W jednym teście mój program daje złą odpowiedź i nie potrafie znaleźć luki (pewnie jakiś przypadek szczególny lub szczegół implementacyjny).
moje rozwiązanie:

Ukryta treść:    

Kod: Zaznacz cały

#include <iostream>
#include<vector.h>

enum COLOR {WHITE, GREY, BLACK};
namespace X
{
vector<COLOR> color;
}
using namespace std;

int DFS_visit( vector< vector<int> > &Adj, vector<int> &d, vector<int> &pi, int u);
int max(int x, int y);
//---------------------------------------------------------------------------

int main()
{
        ios_base::sync_with_stdio(0);
        int n;
        cin>>n;
        vector< vector<int> > Adj(n);
        vector<int> d(n, 1);
        vector<int> pi(n, -1);

        int a,b;
        for(int i(0); i<n-1; ++i)
        {
                cin>>a>>b;
                Adj[a-1].push_back(b-1);
                Adj[b-1].push_back(a-1);
        }

        X::color.resize(n);
        for(int i(0); i<n; ++i)
                X::color[i]=WHITE;

        for(int i(0); i<Adj[0].size(); ++i)
                d[0]+=DFS_visit(Adj, d ,pi, Adj[0][i]);

        int maximum(n-1);
        for(int i(1); i<n; ++i)
        {
                //badanie krawedzi (i,pi[i])
                maximum=max(maximum, d[i]*(n-d[i]));
        }
        cout<<maximum;
        return(0);
}
//---------------------------------------------------------------------------

/*
0,1,2,...,n-1 - wierzcholki grafu
Adj-listy sąsiedztwa
d-ilosc potomków +1
pi-przodek w drzewie przeszukiwania w glab     
*/
//u-wierzcholek poczatkowy
int DFS_visit( vector< vector<int> > &Adj, vector<int> &d,  vector<int> &pi, int u)
{
        X::color[u]=GREY;
        for(int j(0); j<Adj[u].size(); ++j)
        {
              if(X::color[Adj[u][j]]==WHITE)
              {
                pi[Adj[u][j]]=u;
                d[u]+=DFS_visit(Adj, d, pi, Adj[u][j]);
              }
        }

        X::color[u]=BLACK;              //wierzcholek zostal przetworzony
        return(d[u]);
}
//-------------------------------------------------------------------
int max(int x, int y)
{
        if(x>=y) return(x);
        else     return(y);
}

wywołuje troche zmodyfikowanego DFSa (dowolny wierzchołek początkowy) tak aby dla każdego wierzchołka wyznaczyć liczbe jego potomków. Pamiętam też poprzedników w drzewie przeszukiwania w głąb. Na koniec sprawdzam wszystkie krawędzie (są postaci (wierzchołek, poprzednik)) i wyznaczam szukane maximum. Co jest nie tak?-- 22 sierpnia 2009, 11:21 --edit: już znalazłem