#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;

struct TreeNode{        //定義樹節點類型
	string  Name;         //節點名字
	int Value;                //節點的估計值
	vector<int> vect;    //存放子節點下標
	bool haveValue;
	bool isMax;
	bool isMin;
	int dad;    //存放每一個節點的父親節點在vector中的下標
};

vector<TreeNode> vec;
int  n=0;                     //用于記錄要添加子節點的母節點編號
int  cut(TreeNode & t)         //用于剪枝的遞歸函數
{
	if(t.isMax)
	{
		if(t.vect.size()==0)
			return  t.Value;
		else {
			int max=-10000;
			int herecut=-1;
			for(vector<int>::size_type i=0;i<t.vect.size();i++)
			{
				vec[t.vect[i]].Value=cut(vec[t.vect[i]]);
				vec[t.vect[i]].haveValue=true;
				if(max<vec[t.vect[i]].Value)
				{
					  max=vec[t.vect[i]].Value;
			    	  t.Value=max;
		           	  t.haveValue=true;
					  int d=t.dad;
					  while(d!=-1)
					  {
							if(vec[d].isMin&&vec[d].haveValue&&vec[d].Value<max)
							{
								herecut=i;
								break;
							}
							d=vec[d].dad;
					  }
				 }
		    	if(herecut!=-1&&herecut+1<t.vect.size())
				{
					   cout<<"剪枝 :"<<t.Name<<":";
						for(vector<int>::size_type k=herecut+1;k<t.vect.size();k++)
						{cout<<vec[t.vect[k]].Name;}
						cout<<endl;
				}
						if(herecut!=-1)   break;
			}
			
				 return t.Value;
	    }
	}
	else if(t.isMin)
	{
		int min=10000;
		int herecut=-1;
		for(vector<int>::size_type i=0;i<t.vect.size();i++)
		{
			vec[t.vect[i]].Value=cut(vec[t.vect[i]]);
			vec[t.vect[i]].haveValue=true;
			if(min>vec[t.vect[i]].Value)
			{
				min=vec[t.vect[i]].Value;
				 t.Value=min;
		         t.haveValue=true;
				int d=t.dad;
						while(d!=-1){
							if(vec[d].isMax&&vec[d].haveValue&&vec[d].Value>min)
								{
									herecut=i;
									break;
								}
								d=vec[d].dad;
						}
		  	}
		   if(herecut!=-1&&herecut+1<t.vect.size())
			{
				cout<<"剪枝 :"<<t.Name<<":";
				for(vector<int>::size_type k=herecut+1;k<t.vect.size();k++)
				{cout<<vec[t.vect[k]].Name;}
				cout<<endl;
		   }
				if(herecut!=-1)    break;
		}
		 return t.Value;
	}
}

int main(){
	char   fileName[50];
	cin>>fileName;
    ifstream fin(fileName);
	if(!fin){
		cout<<"文件打開失敗"<<endl;
		return 0;
	}
	char Str[30];
	while(fin>>Str){                                    //讀入建樹的循環
		if(strcmp(Str,"ROOT")==0)     
		{
			fin>>Str;
			TreeNode t;
			t.Name=Str;
			t.haveValue=false;
			t.isMax=true;
			t.isMin=false;
			t.dad=-1;
			vec.push_back(t);
			fin>>Str;
		}
		else if(strcmp(Str,"END")==0)
		{
			fin>>Str;
			if(strcmp(Str,"VALUE")==0)
				break;
			for(vector<int>::size_type i=0;i<vec.size();i++)
			{
				if(vec[i].Name==Str)
					n=i;
			}
		}
		else 
		{
			TreeNode t;
			t.Name=Str;
			t.haveValue=false;
			if(vec[n].isMax) 
			{t.isMax=false;
			t.isMin=true;}
			else
			{t.isMax=true;
			t.isMin=false;}
			t.dad=n;
			vec.push_back(t);
			vec[n].vect.push_back(vec.size()-1);
		}
	}
	while(fin>>Str)                        //為葉節點讀入估計值的過程
	{
		if(strcmp(Str,"End")==0)
			break;
		for(vector<int>::size_type i=0;i<vec.size();i++)
		{
			int val=0;
			if(vec[i].Name==Str)
			{
				fin>>val;
			    vec[i].Value=val;
				vec[i].haveValue=true;
			}
		}
	}
//以上步驟已經將該博弈樹的相關信息包括葉節點的估計值、父子關系存入一個vector之中，下面實現剪枝過程（先實現一個極大極小過程）
	   int res=cut(vec[0]);
	   cout<<"根節點:"<< vec[0].Name<<endl;
	   cout<<"倒推值:"<<res<<endl;
	   int m=0;
	   for(vector<int>::size_type i=0;i<vec[0].vect.size();i++)
	   {
		   if(vec[0].Value==vec[vec[0].vect[i]].Value)
		   {  m=i;break;}
	   }
	   cout<<"應走路徑:"<<vec[vec[0].vect[m]].Name<<endl;

	   int y;
	   cout<<"請輸入任意整數以結束程序"<<endl;
	   cin>>y;
	return 0;
}