URAL1039[Anniversary party]

树形动规。

然后，若上司去了，那么下属一定不能去；若上司不去，那么下属可去可不去。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-3-22

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using std::cin;

using std::cout;

#include <fstream>

using std::ifstream;

using std::ofstream;

#include <sstream>

using std::stringstream;

using std::endl;

#include <vector>

using std::vector;

#include <string>

using std::string;

#include <stack>

using std::stack;

#include <queue>

using std::queue;

#include <set>

using std::set;

#include <map>

using std::map;

using std::pair;

using std::make_pair;

#include <algorithm>

using std::sort;

#include <cassert>

//using std::assert;

 

class Application

{

      static const int oo=~(1<<31);

      int N;

      vector<int> happy;

      vector<vector<int> > children;

      vector<vector<int> > f;

      int dp(int parent,bool join)

      {

          if (f[parent][join]!=-oo) return f[parent][join];

          int max=-oo;

          //CASE 1 MY PARENT WANNA JOIN THE PARTY

          if (join)

          {

             int get=happy[parent];

             for (int i=0;i<children[parent].size();i++)

                 get+=dp(children[parent][i],false);

             if (get>max) max=get;

          }

          //CASE 2 MY PARENT HATE PARTIES

          else

          {

             int get=0;

             for (int i=0;i<children[parent].size();i++)

             {

                 int joinit=dp(children[parent][i],true);

                 int hateit=dp(children[parent][i],false);

                 if (joinit>hateit) get+=joinit;

                 else get+=hateit;

             }

             if (get>max) max=get;        

          }

          return f[parent][join]=max;

      }

      public:

      Application()

      {

                    //WE WANNA A ROOT, SO WE ADD A NODE 0.

                    cin>>N;

                    happy.resize(N+1);

                    happy[0]=0;

                    for (int i=1;i<=N;i++)

                        cin>>happy[i];

                    children.resize(N+1);

                    vector<bool> haveParent(N+1,false);

                    for (;;)

                    {

                        int L,K;

                        cin>>L>>K;

                        if (L==0&&K==0) break;

                        children[K].push_back(L);

                        haveParent[L]=true;

                    }

                    for (int i=1;i<=N;i++)

                        if (!haveParent[i])

                           children[0].push_back(i);

      }

      int run()

      {

          f.resize(N+1,vector<int>(2,-oo));

          cout<<dp(0,false)<<endl;

          return 0;

      }

};

 

int main()

{

    Application app;

    return app.run();

}