1734: 堆（DFS）

1734: 堆

时间限制: 1 Sec  内存限制: 128 MB
提交: 678  解决: 310
[提交][状态][讨论版][命题人:admin]

题目描述

输入

输出

样例输入

3
1
10
3
10 5 3
1 2
1 3
5
1 2 3 4 5
3 1
2 1
2 4
2 5

样例输出

Yes
No
Yes

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std ; 

#define maxn 1100
int t ; 
int n ; 
int map[maxn][maxn] ; 
int value[maxn] ; 
bool flag = true ; 
bool visit[maxn] ; 

void DFS(int pos){
    if(!flag){
        return;
    }
    visit[pos] = true ; 
    for(int i=1 ; i<=n ; i++){
        //标记一下防止搜到父节点
        if(map[pos][i]!=0 && !visit[i]){
            if(value[pos] > value[i]){
                flag = false ; 
                break ; 
            }
            DFS(i) ; 
        }
    }
}

int main(){

    cin >> t ; 

    while(t--){
        cin >> n ; 
        flag = true ; 
        for(int i=1 ; i<=n ; i++){
            cin >> value[i] ; 
        }
        memset(map , 0  , sizeof(map)) ; 
        int u , v ; 
        for(int i=1 ; i<=n-1 ; i++){
            cin >> u >> v ; 
            map[u][v] = map[v][u] = 1 ; 
        }

        memset(visit , false , sizeof(visit)) ; 
        DFS(1) ; 

        if(flag){
            cout << "Yes" << endl ; 
        }else {
            cout << "No" << endl ; 
        }
    }

    return 0 ; 
}