/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
/*
使用快慢指针查看是否存在重合节点
然后再找到
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        //注意这里进行检查
        if(!pHead||!pHead->next) return nullptr;
        ListNode *slow=pHead;
        ListNode *fast=pHead;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
            if(slow==fast){
                break;
            }
        }
        if(slow!=fast){
            return nullptr;
        }
        slow=pHead;
        while(slow&&fast){
            if(slow==fast){
                break;
            }
            slow=slow->next;
            fast=fast->next;
        }
        return slow;
    }
};

/*
主要思路：从边界开始对边界的所有值进行BFS
将BFS到的节点都转变为M;
然后将非M的O全部设置为X;
将M设置为O;
*/

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        if(board.empty()) return ;
        for(int i=0;i<board.size();++i){
            if(board[i][0]=='O'){
                BFS(board,i,0);
            }
        }
        for(int i=0;i<board[0].size();++i){
            if(board[0][i]=='O'){
                BFS(board,0,i);
            }
        }
        if(board.size()>1){
            int len=board.size()-1;
            for(int i=0;i<board[0].size();++i){
                if(board[len][i]=='O'){
                    BFS(board,len,i);
                }
            }
        }
        
        if(board[0].size()>1){
            int len=board[0].size()-1;
            for(int i=0;i<board.size();++i){
                if(board[i][len]=='O'){
                    BFS(board,i,len);
                }
            }
        }
        
        for(int i=0;i<board.size();++i){
            for(int j=0;j<board[0].size();++j){
                if(board[i][j]=='O'){
                    board[i][j]='X';
                }
            }
        }
        for(int i=0;i<board.size();++i){
            for(int j=0;j<board[0].size();++j){
                if(board[i][j]=='M'){
                    board[i][j]='O';
                }
            }
        }
        
    };
    int dxdy[4][2]={
        {-1,0},
        {0,-1},
        {1,0},
        {0,1}
    };
    void BFS(vector<vector<char>> &board,int x,int y){
        if(x<0||x>=board.size()||y<0||y>=board[0].size()){
            return ;
        }
        if(board[x][y]!='O') return ;
        board[x][y]='M';
        for(int i=0;i<4;++i){
            int dx=dxdy[i][0];
            int dy=dxdy[i][1];
            BFS(board,x+dx,y+dy);
        }
    }
};

/*
主要思路：使用深度遍历；对每个节点
存储其child 子集和对应的happy值
并进行DFS更新
分为当前去还是不去，去则将查找找孙节点的所有去的子集并添加
不去，则直接计算所有子节点的子集
比较去和不去的最大值

*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Node{
    int happy_val=0;
    int max_happy=0;
    vector<int> childs;
    friend ostream& operator << (ostream &os,const Node & no){
        os<<"happy:"<<no.happy_val<<"max_happy "<<no.max_happy<<"\t";
         os<<"childs: ";
        for(int i=0;i<no.childs.size();++i){
            cout<<"child  "<<"i: "<<no.childs.at(i)<<" ";
        }
        os<<endl;
        return os;
    }
};
//深度遍历返回其最大值
int DFS(vector<Node>& tree,int index)
{
    if(index>=tree.size()||index<=0) return 0;
    auto& temp_node=tree.at(index);
    //页节点直接返回当前值
    if(temp_node.childs.empty()){
        return temp_node.happy_val;
    }
    if(temp_node.max_happy!=0){
        return temp_node.max_happy;
    }
    int sum1=0,sum2=temp_node.happy_val;
    //使用当前节点
    for(int i=0;i<temp_node.childs.size();++i){
        //不使用当前节点
        sum1+=DFS(tree,temp_node.childs.at(i));
        //使用当前节点；计算孙节点
        int child_node=temp_node.childs.at(i);
        for(int j=0;j<tree.at(child_node).childs.size();++j){
            sum2+=DFS(tree,tree.at(child_node).childs.at(j));
        }
    }
    temp_node.max_happy=max(sum1,sum2);
    return temp_node.max_happy;
}
int main(int argc ,char* argv[]){
    
    int n=0;
    int root=1;
    cin>>n>>root;
    vector<Node> tree(n+1);
    int i=0;
    while(i<n)
    {
        cin>>tree.at(i+1).happy_val;
        ++i;
    }
    i=0;
    while(i<n){
        int parent=0,son=0;
        cin>>parent>>son;
        tree.at(parent).childs.emplace_back(son);
        ++i;
    }
    
    cout<<DFS(tree,root)<<endl;
    return 0;
}

/*
主要思路：使用数组作为数据存储结构，
第一个到达的肯定是步数最少的。
*/
#include <iostream>
#include <queue>
#include <stack>
 
using namespace std;
 
#define N 8
 
struct Position
{
	int x;
	int y;
};
 
int PositionToIndex(const Position& pos)
{
	return pos.x * N + pos.y;
}
 
Position IndexToPosition(int index)
{
	Position pos = { index / N, index % N };
	return pos;
}
 
bool IsValid(const Position& pos)
{
	return (pos.x >= 0 && pos.x < N && pos.y >= 0 && pos.y < N);
}
 
int main(int argc, char* argv[])
{
	// 将棋盘延展成一维数组，序号表示当前格子，对应的值表示上一步的格子序号
	int* array = new int[N*N];
	for (int i = 0; i < N*N; i++)
	{
		array[i] = -1;
	}
 
	// 指定起始和结束位置
	Position start, end;
	start.x = 3;
	start.y = 4;
	end.x = N - 1;
	end.y = N - 1;
 
	bool finished = false;
 
	// 用栈存储每一步的序列位置，之后可反转输出
	stack<int> finishSteps;
 
	// 利用队列实现广度优先搜索
	queue<Position> steps;
	steps.push(start);
 
	// 由于是第一步，约定值为-2，表示没有上一步
	array[PositionToIndex(start)] = -2;
 
	// 队列里的数据存储当前能走到的格子，若已为空表示已走完所有的格式，或所能走完的格子
	while (!steps.empty())
	{
		// 取出当前的格子，计算下一步，并将当前格子移出队列
		Position curPos = steps.front();
		int curIndex = PositionToIndex(curPos);
		steps.pop();
 
		// 已走到指定终点
		if (curPos.x == end.x && curPos.y == end.y)
		{
			finishSteps.push(PositionToIndex(end));	// 当前一步入栈
			int lastStep = curIndex;
 
			while (true)
			{
				// 一直找上一步，找到起始点为止
				lastStep = array[lastStep];
				if (lastStep == -2)
				{
					finished = true;
					break;
				}
				else
				{
					finishSteps.push(lastStep);
				}
			}
			break;
		}
 
		// 下一步有8个可走的情况，超出边界，或已探索到的忽略
		Position pos1 = { curPos.x + 1, curPos.y - 2 };
		if (IsValid(pos1))
		{
			int index1 = PositionToIndex(pos1);
			if (array[index1] == -1)
			{
				steps.push(pos1);
				array[index1] = curIndex;
			}
		}
 
		Position pos2 = { curPos.x + 2, curPos.y - 1 };
		if (IsValid(pos2))
		{
			int index2 = PositionToIndex(pos2);
			if (array[index2] == -1)
			{
				steps.push(pos2);
				array[index2] = curIndex;
			}
		}
 
		Position pos3 = { curPos.x + 2, curPos.y + 1 };
		if (IsValid(pos3))
		{
			int index3 = PositionToIndex(pos3);
			if (array[index3] == -1)
			{
				steps.push(pos3);
				array[index3] = curIndex;
			}
		}
 
		Position pos4 = { curPos.x + 1, curPos.y - 2 };
		if (IsValid(pos4))
		{
			int index4 = PositionToIndex(pos4);
			if (array[index4] == -1)
			{
				steps.push(pos4);
				array[index4] = curIndex;
			}
		}
 
		Position pos5 = { curPos.x - 1, curPos.y + 2 };
		if (IsValid(pos5))
		{
			int index5 = PositionToIndex(pos5);
			if (array[index5] == -1)
			{
				steps.push(pos5);
				array[index5] = curIndex;
			}
		}
 
		Position pos6 = { curPos.x - 2, curPos.y + 1 };
		if (IsValid(pos6))
		{
			int index6 = PositionToIndex(pos6);
			if (array[index6] == -1)
			{
				steps.push(pos6);
				array[index6] = curIndex;
			}
		}
 
		Position pos7 = { curPos.x - 2, curPos.y - 1 };
		if (IsValid(pos7))
		{
			int index7 = PositionToIndex(pos7);
			if (array[index7] == -1)
			{
				steps.push(pos7);
				array[index7] = curIndex;
			}
		}
 
		Position pos8 = { curPos.x - 1, curPos.y - 2 };
		if (IsValid(pos8))
		{
			int index8 = PositionToIndex(pos8);
			if (array[index8] == -1)
			{
				steps.push(pos8);
				array[index8] = curIndex;
			}
		}
	}
 
	// 完成，打印
	if (finished)
	{
		while (!finishSteps.empty())
		{
			Position pos = IndexToPosition(finishSteps.top());
			cout << "(" << pos.x << ", " << pos.y << "), ";
			finishSteps.pop();
		}
		cout << endl;
	}
 
	delete[] array;
	system("pause");

	return 0;
}