covid21.cpp

#include <bits/stdc++.h>

using namespace std;

struct subset{int parent,rank;};

struct edge{int u,v,w;};

bool comp(edge a,edge b){
    return a.w < b.w;
}

int find(int a,subset* subsets){
    if(subsets[a].parent==a)return a;
    subsets[a].parent = find(subsets[a].parent,subsets);
    return subsets[a].parent;
}

void Union(int a,int b,subset* subsets){
     a = find(a,subsets),b = find(b,subsets);
    if(subsets[a].rank<subsets[b].rank)
        subsets[a].parent = b;
    else if(subsets[a].rank>subsets[b].rank)
        subsets[b].parent = a;
    else{
        subsets[a].parent = b;
        subsets[b].rank++;
    }
}

void dfs(int u,int *vis,vector<vector<int>>& adj){
    vis[u]=1;
    for(int v:adj[u])
        if(vis[v]==0) dfs(v,vis,adj);
}

int age[100100];
vector<vector<int>> c19;
vector<edge> c21;
int vis[100100];
subset subsets[100100];

int solve(){
    int d1,d2,d3,d4;
    cin >> d1 >> d2 >> d3 >>d4;
    int p,n;
    cin >> p >> n;
    for(int i=0;i<p;i++){
        string s;
        cin >> s;
        age[i] = (s=="OLD");
    }
    c19.assign(p,vector<int>());
    c21 = vector<edge>();
    for(int i=0;i<n;i++){
        int a,b,c;
        cin >> a >> b >> c;
        if(c<=d1){
            c19[a].push_back(b);
            c19[b].push_back(a);
        }
        if(c<=(age[a]?d2:d3)||c<=(age[b]?d2:d3))
            c21.push_back((edge){a,b,c});
    }
    for(int i=0;i<p;i++)vis[i]=0;
    dfs(0,vis,c19);
    int I;
    for(I=0;I<p;I++)
        if(vis[I]==0)break;
    cout << (I==p?"YES ":"NO ");
    for(int i=0;i<p;i++)
        subsets[i] = {i,1};
    sort(c21.begin(),c21.end(),comp);
    int total =0;
    for(int i=0;i<p;i++)vis[i]=0;
    for(edge e : c21){
        if(find(e.u,subsets)==find(e.v,subsets))continue;
        Union(e.u,e.v,subsets);
        total += e.w;
        vis[e.u]=vis[e.v]=1;
    }
    for(I=0;I<p;I++)
        if(vis[I]==0)break;
    cout << ((total<=d4&&I==p)?"YES\n":"NO\n");
    return 0;
}

signed main(){
    int t; cin >> t;
    while(t--)
        solve();
}