题目描述

A国共有 $n$ 个不同的城市和 $n - 1$ 条有向道路。其中 $1$ 号城市是A国的首府，该城市可以通过道路到达任意城市。贝塔星的每个城市都有一个LOGO，每个城市的LOGO可以看作一个小写字母。

小H选择从A国的首府出发，沿着道路前进，然后在某个城市结束自己的旅程。旅行路线中各城市的LOGO，会按访问顺序构成一个小写字母组成的字符串。

现在小H想知道，所有可能的字符串中，字典序最大的字符串是什么？

输入格式

输入的第一行，包含一个正整数 $n$，表示A国城市的数量。

输入的第二行，包含 $n$ 个小写字母，其中第 $i$ 个小写字母表示 $i$ 号城市的LOGO。

接下来 $n - 1$ 行，每行包含两个整数 $u_i, v_i$，依次分别表示一条有向道路的起点和终点。

输出格式

输出仅一行，包含一个字符串，表示字典序最大字符串。

样例 #1

样例输入 #1

5
zbada
1 5
1 3
3 4
5 2

样例输出 #1

zad

样例 #2

样例输入 #2

9
luaatinua
1 2
1 8
2 4
2 3
4 5
5 6
6 7
6 9

样例输出 #2

luatin

提示

$1 \leq u_i, v_i \leq n \leq 10^6$

大样例下载

我的bfs如下

#include<bits/stdc++.h>
using namespace std;
struct point{
    string name,s;
    vector<int> son;
    int maxfather;
};
string add(string a,string b){
    return a + b;
}
vector<point> graph;
int n,u,v;
char c;
string s;

int main(){
    cin>>n;
    graph.resize(n);
    cin>>s;
    for(int i=0;i<n;i++){
        graph[i].name=s[i];
        graph[i].s="";
    }
    for(int i=0;i<n-1;i++){
        cin>>u>>v;
        graph[u-1].son.push_back(v-1);
    }
    priority_queue<unsigned short> q;
    q.push(0);
    graph[0].s=graph[0].name;
    while(!q.empty()){
        int now=q.top();
        q.pop();
        vector<int> maxes;
        string maxe;
        for(auto i:graph[now].son){
            if(graph[i].name==maxe){
                maxes.push_back(i);
                maxe=graph[i].name;
            }
            if(graph[i].name>maxe){
                maxes.clear();
                maxes.push_back(i);
                maxe=graph[i].name;
            }
        }
        for(auto i:maxes){
            if(graph[i].s<add(graph[now].s,graph[i].name)){
                graph[i].s=add(graph[now].s,graph[i].name);
                graph[i].maxfather=now;
                q.push(i);
                //cout<<"Pushed "<<i<<endl;
            }
        }
    }
    string maxs="";
    for(auto i:graph){
        if(i.s>maxs){
            maxs=i.s;
        }
    }
    cout<<maxs<<endl;
    return 0;
}

对于较大的测试点mle