6828085ccd 2015-09-11        kinaba: #include <iostream>
6828085ccd 2015-09-11        kinaba: #include <sstream>
6828085ccd 2015-09-11        kinaba: #include <iomanip>
6828085ccd 2015-09-11        kinaba: #include <vector>
6828085ccd 2015-09-11        kinaba: #include <string>
6828085ccd 2015-09-11        kinaba: #include <map>
6828085ccd 2015-09-11        kinaba: #include <set>
6828085ccd 2015-09-11        kinaba: #include <algorithm>
6828085ccd 2015-09-11        kinaba: #include <numeric>
6828085ccd 2015-09-11        kinaba: #include <iterator>
6828085ccd 2015-09-11        kinaba: #include <functional>
6828085ccd 2015-09-11        kinaba: #include <complex>
6828085ccd 2015-09-11        kinaba: #include <queue>
6828085ccd 2015-09-11        kinaba: #include <stack>
6828085ccd 2015-09-11        kinaba: #include <cmath>
6828085ccd 2015-09-11        kinaba: #include <cassert>
6828085ccd 2015-09-11        kinaba: #include <tuple>
6828085ccd 2015-09-11        kinaba: using namespace std;
6828085ccd 2015-09-11        kinaba: typedef long long LL;
6828085ccd 2015-09-11        kinaba: typedef complex<double> CMP;
6828085ccd 2015-09-11        kinaba: 
6828085ccd 2015-09-11        kinaba: class WalkOverATree { public:
6828085ccd 2015-09-11        kinaba: 	int maxNodesVisited(vector <int> parent, int L)
6828085ccd 2015-09-11        kinaba: 	{
6828085ccd 2015-09-11        kinaba: 		const int N = parent.size() + 1;
6828085ccd 2015-09-11        kinaba: 		vector<vector<int>> G(N);
6828085ccd 2015-09-11        kinaba: 		for(int i=0; i<parent.size(); ++i)
6828085ccd 2015-09-11        kinaba: 			G[parent[i]].push_back(i+1);
6828085ccd 2015-09-11        kinaba: 
6828085ccd 2015-09-11        kinaba: 		vector<int> numBelow(N); {
6828085ccd 2015-09-11        kinaba: 			function<int(int)> rec;
6828085ccd 2015-09-11        kinaba: 			rec = [&](int v) {
6828085ccd 2015-09-11        kinaba: 				int cnt = 1;
6828085ccd 2015-09-11        kinaba: 				for(auto u: G[v])
6828085ccd 2015-09-11        kinaba: 					cnt += rec(u);
6828085ccd 2015-09-11        kinaba: 				return numBelow[v] = cnt;
6828085ccd 2015-09-11        kinaba: 			};
6828085ccd 2015-09-11        kinaba: 			rec(0);
6828085ccd 2015-09-11        kinaba: 		}
6828085ccd 2015-09-11        kinaba: 
6828085ccd 2015-09-11        kinaba: 		function<int(int, int)> rec;
6828085ccd 2015-09-11        kinaba: 		map<pair<int,int>, int> memo;
6828085ccd 2015-09-11        kinaba: 		rec = [&](int v, int L) {
6828085ccd 2015-09-11        kinaba: 			const pair<int,int> key(v, L);
6828085ccd 2015-09-11        kinaba: 			if(memo.count(key)) return memo[key];
6828085ccd 2015-09-11        kinaba: 
6828085ccd 2015-09-11        kinaba: 			const vector<int>& child = G[v];
6828085ccd 2015-09-11        kinaba: 			if(L<=0 || child.empty())
6828085ccd 2015-09-11        kinaba: 				return 1;
6828085ccd 2015-09-11        kinaba: 
6828085ccd 2015-09-11        kinaba: 			int visMax = 0;
6828085ccd 2015-09-11        kinaba: 			for(int i=0; i<child.size(); ++i) {
6828085ccd 2015-09-11        kinaba: 				set<int> previsit;
6828085ccd 2015-09-11        kinaba: 				previsit.insert(0);
6828085ccd 2015-09-11        kinaba: 				for(int k=0; k<child.size(); ++k) if(i!=k) {
6828085ccd 2015-09-11        kinaba: 					set<int> pv2 = previsit;
6828085ccd 2015-09-11        kinaba: 					for(int z: previsit)
6828085ccd 2015-09-11        kinaba: 						pv2.insert(z + numBelow[child[k]]);
6828085ccd 2015-09-11        kinaba: 					previsit = pv2;
6828085ccd 2015-09-11        kinaba: 				}
6828085ccd 2015-09-11        kinaba: 
6828085ccd 2015-09-11        kinaba: 				for(int p: previsit) if(p*2 <= L)
6828085ccd 2015-09-11        kinaba: 					visMax = max(visMax, 1 + p + rec(child[i], L-p*2-1));
6828085ccd 2015-09-11        kinaba: 			}
6828085ccd 2015-09-11        kinaba: 			return memo[key] = visMax;
6828085ccd 2015-09-11        kinaba: 		};
6828085ccd 2015-09-11        kinaba: 		return rec(0, L);
6828085ccd 2015-09-11        kinaba: 	}
6828085ccd 2015-09-11        kinaba: };
6828085ccd 2015-09-11        kinaba: 
6828085ccd 2015-09-11        kinaba: // BEGIN CUT HERE
6828085ccd 2015-09-11        kinaba: #include <ctime>
6828085ccd 2015-09-11        kinaba: double start_time; string timer()
6828085ccd 2015-09-11        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
6828085ccd 2015-09-11        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
6828085ccd 2015-09-11        kinaba:  { os << "{ ";
6828085ccd 2015-09-11        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
6828085ccd 2015-09-11        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
6828085ccd 2015-09-11        kinaba: void verify_case(const int& Expected, const int& Received) {
6828085ccd 2015-09-11        kinaba:  bool ok = (Expected == Received);
6828085ccd 2015-09-11        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
6828085ccd 2015-09-11        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
6828085ccd 2015-09-11        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
6828085ccd 2015-09-11        kinaba: #define END	 verify_case(_, WalkOverATree().maxNodesVisited(parent, L));}
6828085ccd 2015-09-11        kinaba: int main(){
6828085ccd 2015-09-11        kinaba: /*
6828085ccd 2015-09-11        kinaba: CASE(0)
6828085ccd 2015-09-11        kinaba: 	int parent_[] = {0, 0};
6828085ccd 2015-09-11        kinaba: 	  vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_));
6828085ccd 2015-09-11        kinaba: 	int L = 2;
6828085ccd 2015-09-11        kinaba: 	int _ = 2;
6828085ccd 2015-09-11        kinaba: END
6828085ccd 2015-09-11        kinaba: */
6828085ccd 2015-09-11        kinaba: CASE(1)
6828085ccd 2015-09-11        kinaba: 	int parent_[] = {0, 0};
6828085ccd 2015-09-11        kinaba: 	  vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_));
6828085ccd 2015-09-11        kinaba: 	int L = 3;
6828085ccd 2015-09-11        kinaba: 	int _ = 3;
6828085ccd 2015-09-11        kinaba: END
6828085ccd 2015-09-11        kinaba: CASE(2)
6828085ccd 2015-09-11        kinaba: 	int parent_[] = {0, 1, 2, 3};
6828085ccd 2015-09-11        kinaba: 	  vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_));
6828085ccd 2015-09-11        kinaba: 	int L = 2;
6828085ccd 2015-09-11        kinaba: 	int _ = 3;
6828085ccd 2015-09-11        kinaba: END
6828085ccd 2015-09-11        kinaba: CASE(3)
6828085ccd 2015-09-11        kinaba: 	int parent_[] = {0,0,0,0,2,4,2,3,1};
6828085ccd 2015-09-11        kinaba: 	  vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_));
6828085ccd 2015-09-11        kinaba: 	int L = 1;
6828085ccd 2015-09-11        kinaba: 	int _ = 2;
6828085ccd 2015-09-11        kinaba: END
6828085ccd 2015-09-11        kinaba: CASE(4)
6828085ccd 2015-09-11        kinaba: 	int parent_[] = {0,0,1,2,3,2,3,1,3,0,1,8,6,8,0,5,15,0,9};
6828085ccd 2015-09-11        kinaba: 	  vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_));
6828085ccd 2015-09-11        kinaba: 	int L = 4;
6828085ccd 2015-09-11        kinaba: 	int _ = 5;
6828085ccd 2015-09-11        kinaba: END
6828085ccd 2015-09-11        kinaba: CASE(5)
6828085ccd 2015-09-11        kinaba: 	int parent_[] = {0,0,0,1,1,3,5,1,4,5,2,2,10,5,10,10,11,13,8,3,18,15,20,20,23,8,11,26,4};
6828085ccd 2015-09-11        kinaba: 	  vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_));
6828085ccd 2015-09-11        kinaba: 	int L = 26;
6828085ccd 2015-09-11        kinaba: 	int _ = 17;
6828085ccd 2015-09-11        kinaba: END
6828085ccd 2015-09-11        kinaba: CASE(6)
6828085ccd 2015-09-11        kinaba: 	int parent_[] = {0, 0, 2, 0}
6828085ccd 2015-09-11        kinaba: ;
6828085ccd 2015-09-11        kinaba: 	  vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_));
6828085ccd 2015-09-11        kinaba: 	int L = 100;
6828085ccd 2015-09-11        kinaba: 	int _ = 5;
6828085ccd 2015-09-11        kinaba: END
6828085ccd 2015-09-11        kinaba: CASE(7)
6828085ccd 2015-09-11        kinaba: 	int parent_[] = {0, 0, 2};
6828085ccd 2015-09-11        kinaba: 	  vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_));
6828085ccd 2015-09-11        kinaba: 	int L = 4;
6828085ccd 2015-09-11        kinaba: 	int _ = 4;
6828085ccd 2015-09-11        kinaba: END
6828085ccd 2015-09-11        kinaba: CASE(8)
6828085ccd 2015-09-11        kinaba: 	int parent_[] = {0,1,2,0,4,4,4,4};
6828085ccd 2015-09-11        kinaba: 	  vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_));
6828085ccd 2015-09-11        kinaba: 	int L = 3;
6828085ccd 2015-09-11        kinaba: 	int _ = 4;
6828085ccd 2015-09-11        kinaba: END
6828085ccd 2015-09-11        kinaba: CASE(9)
6828085ccd 2015-09-11        kinaba: 	int parent_[] = {0,0,2,0,4,5};
6828085ccd 2015-09-11        kinaba: 	  vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_));
6828085ccd 2015-09-11        kinaba: 	int L = 7;
6828085ccd 2015-09-11        kinaba: 	int _ = 6;
6828085ccd 2015-09-11        kinaba: END
6828085ccd 2015-09-11        kinaba: }
6828085ccd 2015-09-11        kinaba: // END CUT HERE