Jimi Hendrix

input/code.cpp: In function 'int main()':
input/code.cpp:101:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; 2*i < s.size(); ++i) {
                                 ^

#include <vector>
#include <cstring>
#include <iostream>
#define F first
#define S second
using namespace std;
const int MN = 5e5+100;
vector<pair<int, char> > v[MN];
int dp[MN];
bool used[MN];
int n,m;
string s;
void f1(int x) {
    used[x] = 1;
    for(auto y: v[x]) {
        if(!used[y.F]) {
            f1(y.F);
            int q = dp[y.F];
            if(q < m && y.S == s[q]) {
                dp[x] = max(dp[x], dp[y.F]+1);
            }
            dp[x] = max(dp[x], dp[y.F]);
        }
    }
}
int f2(int x, int up) {
    pair<int, int> b1 = {up, -1};
    pair<int, int> b2 = {0, -1};
    used[x] = 1;
    for(auto y: v[x]) {
        if(!used[y.F]) {
            int q = dp[y.F];
            if(q < m && y.S == s[q]) {
                ++q;
            }
            if(q > b1.F) {
                b2 = b1;
                b1 = {q, y.F};
            }
            else if(q > b2.F) {
                b2 = {q, y.F};
            }
        }
    }
    if(b1.F == m) {
        return x;
    }
    for(auto y: v[x]) {
        if(!used[y.F]) {
            int nUp;
            if(b1.S == y.F) {
                nUp = b2.F;
            }
            else {
                nUp = b1.F;
            }
            if(nUp < m && y.S == s[nUp]) {
                ++nUp;
            }
            int q = f2(y.F, nUp);
            if(q != -1) return q;
        }
    }
    return -1;
}
int f3(int x, int q) {
    used[x] = 1;
    if(q == m) {
        return x;
    }
    for(auto y: v[x]) {
        if(!used[y.F]) {
            int nq = q;
            if(y.S == s[q]) {
                ++nq;
            }
            int w = f3(y.F, nq);
            if(w != -1) return w;
        }
    }
    return -1;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i = 0; i < n-1; ++i) {
        int a,b;
        char c;
        cin>>a>>b>>c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    cin>>s;
    f1(1);
    memset(used, 0, sizeof used);
    int root = f2(1, 0);
    if(root == -1) {
        cout<<-1<<' '<<-1<<endl;
    }
    for(int i = 0; 2*i < s.size(); ++i) {
        swap(s[i], s[(int)s.size()-1-i]);
    }
    memset(used, 0, sizeof used);
    int q = f3(root, 0);
    cout<<q<<' '<<root<<endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED